Prefix Sums

Tier II · Intermediate

Precomputed running totals and difference arrays for O(1) range queries.

0 / 7 clearedBronzeShow difficulty×2SilverShow difficulty×5Core×1

Primer

A prefix array stores running totals where P[i] is the sum of the first i elements. Any range sum is the difference of two prefix totals, which turns every range query into a single subtraction.

Range sums from a prefix array

Six numbers. The goal is the sum of any slice with a single subtraction, however long the slice is.

Step 1 / 11

Watch P get built once, then two slices answered with one subtraction each. Everything before the slice is in both totals, so it cancels out.

Variant	What it precomputes	Typical use
Prefix sum	Running totals `P[0..n]`	Range sums, suffixes
Difference array	Neighbor differences	Batched range updates
Prefix + hash map	Prefix value counts	Counting subarrays by sum

The usual slip is the off-by-one. Store a leading zero, P[0] = 0, and the inclusive range [l, r] becomes P[r+1] - P[l] with no special case at the front. The difference array is the inverse of the prefix array. You add d at start, subtract it at end + 1, and one prefix pass recovers all the final values.

Approach	Time	Extra space
Re-add per query	$O(nq)$	$O(1)$
Prefix sums	$O(n + q)$	$O(n)$
Difference array, $m$ updates	$O(n + m)$	$O(n)$

Reach for it when a problem asks for many range totals, how one part compares with the rest, how a batch of range updates nets out, or how many subarrays hit a target sum or remainder.

The problems below start with range-sum queries and finding a balance point, move through prefix products, the difference array, and 2D grid sums, and end with counting subarrays by sum and by remainder.

Problems7

1
Range Sum QueriesBronzeShow difficultyCore
2
Balance Point IndexBronzeShow difficulty
3
Product of All Other ElementsSilverShow difficulty
4
Range Cyclic Letter ShiftsSilverShow difficulty
5
Square Neighborhood SumsSilverShow difficulty
6
Count Subarrays With Sum KSilverShow difficulty
7
Count Subarrays Divisible by LengthSilverShow difficulty