Prefix Sum
Prefix sum is an auxiliary array prefix where prefix[i] = the sum of the first i elements, with the convention prefix[0] = 0. You build it once with a single O(n) loop.
Once you have the prefix array, the sum of any range [l, r] is available immediately: prefix[r + 1] − prefix[l] — each query costs O(1) instead of re-adding from the start.
An important variant: combine it with a Hash Map to count the subarrays whose sum equals K — as you scan, store how many times each prefix value has appeared; a subarray ending at the current position has sum K if and only if an earlier prefix equal to sum − K exists. This works even when the array contains negative numbers — a case Sliding Window can't handle.
Like the kilometer markers along a highway — each marker shows the distance from the starting point.
- To know how long the stretch between km 120 and km 350 is, just subtract 120 from 350; there is no need to re-measure it meter by meter.
- Compute once up front, look it up forever.
How to spot it
When you see these cues in the problem, reach for Prefix Sum
| Keyword in the problem | Why it points to this topic |
|---|---|
| repeated range-sum queries | Precompute prefix sums, each query becomes O(1) |
| count subarrays summing to K | Prefix sum + Hash Map of seen prefixes |
| array contains negatives | Sliding Window breaks — sums are not monotonic |
| aggregate excluding current element | Combine a left prefix pass with a right suffix pass |
When to use
4 typical situations where this topic applies
Many range-sum queries [l, r] on an array that does not change
Counting / finding subarrays whose sum equals K, is divisible by K, or meets a condition on the sum (combined with a Hash Map)
The array has negative numbers, so Sliding Window does not apply
2D problems: the sum of a rectangular region in a matrix (2D prefix sum)
Prefix / suffix products — the same idea, with multiplication in place of addition
When NOT to use
3 situations where this topic doesn't fit — know them so you don't overuse them
The array is updated often: every single-element change forces rebuilding the whole prefix array — use a Fenwick tree / Segment tree
Only one query: adding directly in O(n) is enough, building a prefix array gains nothing
You need the min / max of a range instead of the sum: min/max has no inverse operation, so use a Sparse Table or Segment tree
Code template
Most problems in this topic share this scaffold — copy it, then fill in the problem-specific logic.
function prefixSumPattern(nums: number[]): R {
// prefix[i] = sum of nums[0..i-1]; prefix[0] = 0
const prefix = new Array(nums.length + 1).fill(0)
for (let i = 0; i < nums.length; i++) {
prefix[i + 1] = prefix[i] + nums[i]
}
// Range sum [l, r] = prefix[r + 1] - prefix[l] — O(1) per query
return answerQueries(prefix)
}Recap
A quick summary — reread it before your interview
Key points
prefix[0] = 0, prefix[i] = prefix[i−1] + nums[i−1] — the prefix array has length n+1 so no special-casing is needed
Range sum [l, r] = prefix[r + 1] − prefix[l]
Counting subarrays with sum K: a Hash Map stores how many times each prefix has appeared; look up sum − K at each step
It stays correct with negative numbers — an advantage over Sliding Window
Common mistakes
Index drift from forgetting the prefix[0] = 0 convention (the prefix array must have length n+1)
Using Sliding Window for a "sum equals K" problem when the array has negatives — the window resizes incorrectly because the sum is no longer monotonic
Forgetting to initialize map.set(0, 1) (the empty prefix) → misses subarrays that start at index 0
Complexity
tiền xử lý O(n), mỗi truy vấn O(1)Practice problems for this topic
Grouped by difficulty — work through them in order to build confidence