Envío 515

Código

package main

import (
	"fmt"
)

func solve(a, s []int, p, q int) {
	// O(n) -- too slow!
	// sum := 0
	// for i := p; i <= q; i++ {
	// 	sum += a[i]
	// }

	// O(1)
	sum := s[q]  // a[0] + a[1] + ... + a[q]
	if (p - 1 >= 0) {
		sum -= s[p - 1]
	}

	fmt.Println(sum)
}

func main() {
	var n int
	_, err := fmt.Scanf("%d", &n)
	if err != nil {
		panic(err)
	}

	a := make([]int, n)
	for i := 0; i < n; i++ {
		_, err := fmt.Scanf("%d", &a[i])
		if err != nil {
			panic(err)
		}
	}


	s := make([]int, n)
	// for i := 0; i < n; i++ {
	// 	s[i] = a[i]
	// 	if i - 1 >= 0 {
	// 		s[i] += s[i - 1]
	// 	}
	// }


	// O(n)
	sum := 0
	for i := 0; i < n; i++ {
		sum += a[i]
		s[i] = sum
	}


	var c int
	_, err = fmt.Scanf("%d", &c)
	if err != nil {
		panic(err)
	}

	for k := 0; k < c; k++ {
		var p, q int
		_, err := fmt.Scanf("%d %d", &p, &q)
		if err != nil {
			panic(err)
		}

		solve(a, s, p, q)
	}
}