Prefix Sum

Build a prefix sum array in O(n), then answer any range sum query in O(1). The extra zero at the front makes the formula work cleanly for all ranges.

package main

import "fmt"

func buildPrefix(nums []int) []int {
	prefix := make([]int, len(nums)+1)
	for i, n := range nums {
		prefix[i+1] = prefix[i] + n
	}
	return prefix
}

func rangeSum(prefix []int, i, j int) int {
	return prefix[j+1] - prefix[i]
}

func main() {
	nums := []int{2, 4, 1, 3, 5}
	prefix := buildPrefix(nums)
	fmt.Println(prefix) // [0 2 6 7 10 15]

	fmt.Println(rangeSum(prefix, 1, 3)) // 8  (4 + 1 + 3)
	fmt.Println(rangeSum(prefix, 0, 4)) // 15 (2 + 4 + 1 + 3 + 5)
	fmt.Println(rangeSum(prefix, 2, 2)) // 1  (just nums[2])
}