Prefix Sum

One-liner: precompute running totals once, so the sum of any range becomes a single subtraction.

The analogy

Think of a car's odometer. To know how far you drove between two gas stations you do not re-measure the road — you read the odometer at each stop and subtract. A prefix sum array is an odometer for your data: prefix[i] is the total up to position i, and any range sum is prefix[right+1] - prefix[left]. Pay O(n) once, then every query is O(1).

Recognition signals

Reach for prefix sums when you see:

1. Many range queries (sum of a segment) on data that does not change between queries.
2. A question about contiguous subarrays and their sum (or count, or product) — especially "how many subarrays sum to k".
3. Negative numbers are allowed, so a sliding window cannot decide when to shrink.
4. You catch yourself writing a nested loop whose inner loop just re-adds the same elements.

Step-by-step walkthrough

Take Subarray Sum Equals K on [1, 2, 3] with k = 3:

1. Start with a map {0: 1} — the empty prefix has total 0, seen once.
2. Add 1: running total 1. Look up 1 - 3 = -2 — nothing. Record total 1.
3. Add 2: running total 3. Look up 3 - 3 = 0 — found once, so subarray [1, 2] counts. Record total 3.
4. Add 3: running total 6. Look up 6 - 3 = 3 — found once, so subarray [3] counts.

Answer: 2. Each step asks one question: "how many earlier prefixes sit exactly k below me?"

Code template

Build the array with one extra leading zero. That zero removes every "what if the range starts at index 0" special case.

// Build returns prefix where prefix[i] = sum of nums[0:i] (length n+1).
// The sum of nums[l..r] (inclusive) is then prefix[r+1] - prefix[l].
func Build(nums []int) []int {
	prefix := make([]int, len(nums)+1) // prefix[0] = 0: the empty prefix
	for i, v := range nums {
		prefix[i+1] = prefix[i] + v
	}
	return prefix
}

Why each part exists:

Solutions

Range sum queries

The direct use: build once, answer many.

// NumArray: answer many range-sum queries in O(1) each.
type NumArray struct{ prefix []int }

func NewNumArray(nums []int) *NumArray { return &NumArray{prefix: Build(nums)} }

// SumRange returns the sum of nums[left..right] inclusive.
func (a *NumArray) SumRange(left, right int) int {
	return a.prefix[right+1] - a.prefix[left]
}

Subarray sum equals k

Here we do not even store the array. We keep a map from running total to how many times we have seen it, and ask for sum - k at each step. It works with negatives and zeros because we count every matching earlier prefix, not just one.

// SubarraySum: count subarrays whose sum equals k. Negatives allowed.
// Keep a map of "how many times have I seen each running total".
func SubarraySum(nums []int, k int) int {
	seen := map[int]int{0: 1} // the empty prefix, so subarrays starting at 0 count
	sum, count := 0, 0
	for _, v := range nums {
		sum += v
		count += seen[sum-k] // every earlier prefix equal to sum-k ends a valid subarray here
		seen[sum]++
	}
	return count
}

Product of array except self

The same idea with multiplication: a prefix product from the left times a suffix product from the right. No division, so zeros are harmless.

// ProductExceptSelf: out[i] = product of every element except nums[i], no division.
// A prefix PRODUCT from the left, then a suffix product from the right.
func ProductExceptSelf(nums []int) []int {
	out := make([]int, len(nums))
	run := 1
	for i := range nums {
		out[i] = run // product of everything left of i
		run *= nums[i]
	}
	run = 1
	for i := len(nums) - 1; i >= 0; i-- {
		out[i] *= run // multiply by everything right of i
		run *= nums[i]
	}
	return out
}

Equal zeros and ones

Relabel 0 as -1. Equal counts means a range summing to zero, i.e. two equal prefixes. For the longest range, store only the first index of each total.

// FindMaxLength: longest subarray with equal numbers of 0s and 1s.
// Treat 0 as -1; equal counts means a zero-sum range, so remember the FIRST index of each total.
func FindMaxLength(nums []int) int {
	first := map[int]int{0: -1}
	sum, best := 0, 0
	for i, v := range nums {
		if v == 0 {
			sum--
		} else {
			sum++
		}
		if j, ok := first[sum]; ok {
			best = max(best, i-j)
		} else {
			first[sum] = i
		}
	}
	return best
}

Two dimensions (optional)

Inclusion-exclusion: add the top and left prefixes, subtract the doubly counted corner.

// NumMatrix: 2D prefix sums, O(1) rectangle queries.
type NumMatrix struct{ p [][]int }

func NewNumMatrix(m [][]int) *NumMatrix {
	rows := len(m)
	cols := 0
	if rows > 0 {
		cols = len(m[0])
	}
	p := make([][]int, rows+1)
	for i := range p {
		p[i] = make([]int, cols+1)
	}
	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			p[r+1][c+1] = m[r][c] + p[r][c+1] + p[r+1][c] - p[r][c]
		}
	}
	return &NumMatrix{p: p}
}

// SumRegion sums the rectangle from (r1,c1) to (r2,c2) inclusive.
func (n *NumMatrix) SumRegion(r1, c1, r2, c2 int) int {
	return n.p[r2+1][c2+1] - n.p[r1][c2+1] - n.p[r2+1][c1] + n.p[r1][c1]
}

Complexity

Common mistakes

Practice ladder

Ordered Easy → Hard. None of the titles say "prefix". Ask: is a range total being recomputed?

1. 1.
   Range Sum Query - Immutable

   Many queries, data never changes.
   Easy
2. 2.
   Find Pivot Index

   Left total versus right total at each position.
   Easy
3. 3.
   Subarray Sum Equals K

   Negatives are allowed — two earlier totals differ by k.
   Medium
4. 4.
   Product of Array Except Self

   Division is not allowed. What do you know from each side?
   Medium
5. 5.
   Contiguous Array

   Relabel one value so "equal" becomes "sums to zero".
   Medium
6. 6.
   Range Sum Query 2D - Immutable
   Medium
7. 7.
   Subarray Sums Divisible by K

   Two totals with the same remainder.
   Medium
8. 8.
   Number of Submatrices That Sum to Target

   Fix two rows, then reduce to a 1D problem you already know.
   Hard

Which pattern? Drills

Unlabeled problems — pick the pattern, then read why.