Skip to content

2.2 Prefix Sums

Prefix sums are a preprocessing technique for answering repeated range sum queries on an array.

algorithms computer-science arrays strings

Prefix sums are a preprocessing technique for answering repeated range sum queries on an array. Instead of summing a range from scratch each time, we build an auxiliary array that stores cumulative totals. After this preprocessing step, each range sum can be computed in constant time.

Problem

You have an array A of length n. You need to answer many queries of the form:

sum of A[l] through A[r]

A direct loop costs O(r - l + 1) per query. If there are many queries, this repeated work becomes expensive.

Solution

Build a prefix array P where P[i] stores the sum of the first i elements:

P[0] = 0
P[1] = A[0]
P[2] = A[0] + A[1]
...
P[n] = A[0] + A[1] + ... + A[n-1]

In general:

P[i + 1] = P[i] + A[i]

Then the sum of A[l] through A[r] is:

P[r + 1] - P[l]

Implementation 

func PrefixSums(a []int) []int {
	p := make([]int, len(a)+1)

	for i := 0; i < len(a); i++ {
		p[i+1] = p[i] + a[i]
	}

	return p
}

func RangeSum(p []int, l, r int) int {
	return p[r+1] - p[l]
}

Example:

a := []int{3, 1, 4, 1, 5, 9}
p := PrefixSums(a)

fmt.Println(RangeSum(p, 1, 3)) // 1 + 4 + 1 = 6
fmt.Println(RangeSum(p, 0, 5)) // 3 + 1 + 4 + 1 + 5 + 9 = 23

Why It Works

The prefix value P[r + 1] contains the sum of all elements before index r + 1:

A[0] + A[1] + ... + A[r]

The prefix value P[l] contains the sum of all elements before index l:

A[0] + A[1] + ... + A[l - 1]

Subtracting removes the part before l, leaving only:

A[l] + A[l + 1] + ... + A[r]

Therefore:

RangeSum(l, r) = P[r + 1] - P[l]

Invariant

During construction, after processing indices 0 through i - 1, the prefix array satisfies:

P[i] = A[0] + A[1] + ... + A[i - 1]

Initially, P[0] = 0, which is the sum of zero elements.

At step i, we set:

P[i + 1] = P[i] + A[i]

So P[i + 1] becomes the sum of the first i + 1 elements. This preserves the invariant.

Complexity

Building the prefix array takes:

O(n)

Each range query takes:

O(1)

The extra space is:

O(n)

This is useful when the number of range queries is large enough to justify preprocessing.

Common Boundary Convention

The cleanest convention uses a prefix array of length n + 1.

P[0] = 0
P[i + 1] = P[i] + A[i]

This avoids a special case for ranges starting at index 0.

Without this convention, code often becomes more error prone:

if l == 0 {
	return prefix[r]
}
return prefix[r] - prefix[l-1]

The n + 1 convention removes that branch.

Handling Empty Ranges

With half-open intervals, a range is written as:

[l, r)

meaning it includes l and excludes r.

The sum is:

P[r] - P[l]

This convention also supports empty ranges. If l == r, then:

P[r] - P[l] = 0

This is often the safest form for library code.

func RangeSumHalfOpen(p []int, l, r int) int {
	return p[r] - p[l]
}

Negative Numbers

Prefix sums work with negative numbers. The method depends only on addition and subtraction, not on monotonicity.

a := []int{5, -2, 7, -3}
p := PrefixSums(a)

fmt.Println(RangeSum(p, 1, 3)) // -2 + 7 + -3 = 2

This differs from sliding window techniques, which often require nonnegative values to maintain monotonic behavior.

Two-Dimensional Prefix Sums

For a matrix A, prefix sums can be extended to answer rectangle sum queries.

Define P with one extra row and one extra column:

P[i + 1][j + 1]

stores the sum of the rectangle from (0, 0) through (i, j).

Construction:

func PrefixSums2D(a [][]int) [][]int {
	rows := len(a)
	cols := 0
	if rows > 0 {
		cols = len(a[0])
	}

	p := make([][]int, rows+1)
	for i := range p {
		p[i] = make([]int, cols+1)
	}

	for i := 0; i < rows; i++ {
		for j := 0; j < cols; j++ {
			p[i+1][j+1] = a[i][j] +
				p[i][j+1] +
				p[i+1][j] -
				p[i][j]
		}
	}

	return p
}

Rectangle query for rows [r1, r2) and columns [c1, c2):

func RectSum(p [][]int, r1, c1, r2, c2 int) int {
	return p[r2][c2] -
		p[r1][c2] -
		p[r2][c1] +
		p[r1][c1]
}

The subtraction removes the area above and the area to the left. Their overlap was subtracted twice, so it is added back once.

Common Pitfalls

Using inclusive ranges inconsistently is the most common bug. Decide whether your API uses [l, r] or [l, r) and keep it fixed.

Forgetting the extra zero at the beginning causes special cases at index 0.

Using int may overflow when values or arrays are large. Use int64 when sums may exceed the machine integer range.

Assuming prefix sums require positive numbers is incorrect. They work with any values where addition and subtraction are valid.

Confusing prefix sums with sliding windows leads to wrong algorithms. Prefix sums answer fixed range sum queries. Sliding windows maintain a moving range under additional constraints.

Takeaway

Prefix sums trade O(n) preprocessing and O(n) space for O(1) range sum queries. Use the n + 1 array convention and half-open intervals when possible. The result is simpler code, fewer boundary cases, and a direct invariant for correctness.