What a partial sum is
A partial sum (also called a prefix sum) is the sum of the first few elements of a slice. For nums = [3, -1, 4, 1], the partial sums are 3, 2, 6 and 7: the sum of the first element, of the first two, of the first three and of all four.
The idea is useful because one cheap precomputation answers a whole family of questions. Once the partial sums exist, the sum of any contiguous block of elements, called a subarray, is a single subtraction instead of a loop. This chapter uses that to solve problems on subarray sums in linear time.
Building the prefix array in Go
The convention that keeps the code free of special cases is to make the prefix slice one element longer than the input. Entry prefix[i] holds the sum of the first i elements, so prefix[0] is 0, the sum of nothing.
func buildPrefix(nums []int) []int {
prefix := make([]int, len(nums)+1)
for i, v := range nums {
prefix[i+1] = prefix[i] + v
}
return prefix
}
Here make([]int, n) creates a slice of n zeros, so prefix[0] is already 0. The loop uses for i, v := range nums, which gives the index and the value together. Each new entry is the previous entry plus one more element. For nums = [3, -1, 4, 1, 5, 9, -2, 6] the function returns:
[0 3 2 6 7 12 21 19 25]
Answering range queries
To get the sum of nums[l] through nums[r], both inclusive, subtract the sum before l from the sum up to and including r:
func rangeSum(prefix []int, l, r int) int {
return prefix[r+1] - prefix[l]
}
On the same example, rangeSum(prefix, 2, 5) is prefix[6] - prefix[2] = 21 - 2 = 19, which matches 4 + 1 + 5 + 9. The whole slice is rangeSum(prefix, 0, 7), which gives 25, and a single element is a range with l == r: rangeSum(prefix, 3, 3) gives 1.
The extra leading zero is what makes the first element work. Without it, a range starting at index 0 would need an if to avoid reading prefix[-1]. Go has no negative indexing, so that read would be a panic.
The cost is O(n) once to build the array, then O(1) per query. A loop that sums each range directly costs O(n) per query, which becomes O(n * q) for q queries.
Prefix sums without storing the array
Many problems only need the running total as the scan advances, not the whole array. Then a single variable is enough:
sum := 0
for _, v := range nums {
sum += v
// sum is now the partial sum up to and including v
}
If the original values are no longer needed, the slice can also be turned into its own running totals:
run := []int{1, 2, 3, 4}
for i := 1; i < len(run); i++ {
run[i] += run[i-1]
}
fmt.Println(run) // [1 3 6 10]
This version has no leading zero, and it destroys the original values, which makes recovering one element a subtraction.
Where partial sums lead: subarray problems
The key identity is that a subarray sum is a difference of two prefix sums. That turns questions about subarrays into questions about pairs of prefix values:
- Largest subarray sum. For each end position, the best subarray ending there uses the smallest earlier prefix sum. Track the running total and the smallest total seen so far, and take the largest difference.
- Subarrays with a given sum
k. A subarray ending at the current position has sumkwhen an earlier prefix sum equalssum - k. A map from prefix value to how many times it occurred answers this in one pass.
The second idea looks like this in Go:
arr := []int{1, 2, 3, -3, 3}
k := 3
seen := map[int]int{0: 1}
sum, count := 0, 0
for _, v := range arr {
sum += v
count += seen[sum-k]
seen[sum]++
}
fmt.Println(count) // 5
The map starts with {0: 1}, the empty prefix, so subarrays that begin at index 0 are counted. Reading a missing key from a Go map gives the zero value, 0, so seen[sum-k] needs no existence check and seen[sum]++ works on a new key. The five subarrays found are [1, 2], [3], [1, 2, 3, -3], [3, -3, 3] and the final [3].
Go-specific details and common mistakes
- Off-by-one shifts. With the leading-zero convention,
prefix[i]coversnums[0..i-1]. The rangel..rinclusive isprefix[r+1] - prefix[l], notprefix[r] - prefix[l]. Pick one convention and keep it. - Forgetting the extra slot.
make([]int, len(nums))without the+1panics on the last write,prefix[i+1], with an index out of range. - Integer size.
intis 64 bits on common 64-bit platforms, so sums of ordinary test inputs don't overflow. A sum beyond the range of the type wraps around silently, with no error. For example, anint32holding 2147483647 becomes -2147483648 after adding 1. - Initialising a best sum at 0. If every element is negative, the best subarray sum is negative. Start from a real subarray sum such as
nums[0]. - Modifying the input. Slices share their backing array, so the in-place running total changes the caller's data too.
Key takeaways
- A prefix array with a leading 0 has
len(nums) + 1entries, andprefix[i]is the sum of the firstielements. - The sum of
nums[l..r]isprefix[r+1] - prefix[l], inO(1)afterO(n)preparation. - Often the running total in a single variable is enough, and the subarray problems that follow need only that.
- A map from prefix value to count turns "subarrays with sum
k" into one pass.