Prefix Techniques
Precompute cumulative information so range questions become constant-time differences.
The idea
A prefix-sum array stores running totals so the sum of any contiguous range becomes a single subtraction. Building it costs one pass; every subsequent range-sum query is O(1) instead of O(n).
The same idea generalises: prefix XOR, prefix counts, difference arrays for range updates, and 2-D prefix sums for submatrix queries. Pairing prefix sums with a hash map (prefix-sum-to-index) also solves 'subarray with sum k' in linear time.
A book's running page count. To know how many pages chapters 3–7 span, you subtract the cumulative count before chapter 3 from the cumulative count through chapter 7 — no need to re-add each chapter.
When to reach for it
- Many range-sum / range-aggregate queries over a static array.
- Counting subarrays with a target sum (with a hash map).
- Range updates via a difference array.
Language-independent template
prefix[0] = 0
for i in range(n):
prefix[i + 1] = prefix[i] + arr[i]
range_sum(l, r) = prefix[r + 1] - prefix[l]Complexity — time O(n) build, O(1) query, space O(n).
Common mistakes
- Off-by-one between
prefix[i](exclusive) and array indices. - Sizing the prefix array n instead of n+1 and losing the empty-prefix base.
- Rebuilding the prefix array per query instead of once.
Practice progression
Canonical interview problems, ordered from foundation to advanced application.
Answer repeated inclusive range-sum queries.
Count contiguous subarrays whose sum equals k.
Count subarray sums lying inside an inclusive interval.