Prefix sums

A billing report stores one net usage total per day, including negative adjustments. Finance asks for last week, the first half of the month, and several overlapping campaign periods. Each answer is simple; repeatedly adding the same days is the waste.

The values stay fixed while this report runs. Prefix sums use that pause in updates to prepare one table and turn each later range total into a subtraction.

The report keeps asking for overlapping days

Prefix sums store totals at boundaries: prefix[i] covers positions before i. The leading zero makes empty ranges and ranges starting at zero ordinary cases. Subtracting two boundary totals removes exactly the unwanted prefix, even when values are negative.

Subtracting two saved boundaries

For [3, -2, 5, 4], cumulative totals at the boundaries are [0, 3, 1, 6, 10]. The range [1, 4) is 10 - 3 = 7: both saved totals include day zero, so subtraction removes it. The leading zero handles a range starting at the beginning, and subtracting a boundary from itself gives an empty range's zero total. Negative adjustments don't affect the cancellation argument.

values := []int{3, -2, 5, 4}
prefix := make([]int, len(values)+1)
for index, value := range values {
	prefix[index+1] = prefix[index] + value
}
left, right := 1, 4
fmt.Println(prefix[right] - prefix[left]) // 7
fmt.Println(prefix[2] - prefix[2])        // 0: an empty range

When the ledger changes

Repeated scans cost O(nq), while preprocessing costs O(n) then each sum O(1). This is useful for immutable time-series totals. An update invalidates many prefixes; Fenwick trees handle interleaved updates. Prefix minima cannot be subtracted because minimum has no inverse. Validate bounds explicitly before indexing; Go indexing panics are not the documented error API.

For n values and q queries, independent scans cost O(nq) in the worst case. One O(n) prefix table reduces the total to O(n+q), with O(1) work per query and O(n) auxiliary storage beyond the returned answers. Updates invalidate this static preparation.

Finance can request another interval against the same billing snapshot without scanning those days again.