What a prefix sum is
Back to the fitness app from the Arrays lesson: one user's daily steps (in thousands) are
[7, 3, 9, 4, 12, 6], and the dashboard keeps asking "total steps from day i to day j?" — for every chart, every widget, thousands of times. Re-adding each range works, but it is an O(n) walk per question, and most of those walks re-add the same numbers the last question just added.A prefix sum kills the repetition. Build one extra array where
prefix[i] holds the running total of the first i values — with a 0 parked at the front:prefix[0] = 0(sum of nothing)prefix[1] = 7(first value)prefix[2] = 7 + 3 = 10(first two)- … up to
prefix[6] = 41(all six)
Why the leading zero? So that "everything before index
i" always has an answer — even for i = 0. Once the array exists, any range sum is one subtraction: everything up to the range's end, minus everything before its start. That's the whole trick.Quick check
prefix holds running totals of [7, 3, 9, 4, 12, 6] with a leading 0. Predict prefix[3].
Answer it in the interactive lesson to keep your progress.
How it works, step by step
Two phases: build once, then subtract per query.
Phase 1 — build (one pass)
Start with
[0] and push previous total + next value, one value at a time, for days = [7, 3, 9, 4, 12, 6]:| step | value in | new entry | prefix so far |
|---|---|---|---|
| 1 | 7 | 0 + 7 = 7 | [0, 7] |
| 2 | 3 | 7 + 3 = 10 | [0, 7, 10] |
| 3 | 9 | 10 + 9 = 19 | [0, 7, 10, 19] |
| 4 | 4 | 19 + 4 = 23 | [0, 7, 10, 19, 23] |
| 5 | 12 | 23 + 12 = 35 | [0, 7, 10, 19, 23, 35] |
| 6 | 6 | 35 + 6 = 41 | [0, 7, 10, 19, 23, 35, 41] |
Phase 2 — query (one subtraction)
Total steps for days at indices
2..4? Take everything up to the end of the range, remove everything before its start: Here that is prefix[5] - prefix[2] = 35 - 10 = 25 — and indeed 9 + 4 + 12 = 25, without touching those three values at all. The subtraction works because both entries share the same first two values (7 + 3 = 10), so subtracting cancels everything before the range.In the animation, watch the same two phases: each build step highlights one incoming value and writes one new total, then the query marks the range with
l and r+1 pointers and answers with a single subtraction. Before each build step, predict the next entry. In JavaScript, both phases:This section has a step-by-step animation in the interactive lesson.
const days = [7, 3, 9, 4, 12, 6];
const prefix = [0];
for (const x of days) {
prefix.push(prefix[prefix.length - 1] + x);
}
console.log(prefix.join(',')); // 0,7,10,19,23,35,41
console.log(prefix[5] - prefix[2]); // 25 (sum of indices 2..4)Quick check
Using prefix = [0, 7, 10, 19, 23, 35, 41], predict the sum of indices 0..2.
Answer it in the interactive lesson to keep your progress.
Where it breaks (and how not to get burned)
- The off-by-one.
sum(l..r)isprefix[r + 1] - prefix[l]— end index plus one. Writingprefix[r] - prefix[l]silently drops the last value of the range. If an answer looks short by exactly one element, this is why. - Skipping the leading 0. Without the
0up front, every range that starts at index0needs a special case. The extra slot is not decoration — it is the formula working uniformly. - The data changes. A prefix array is a snapshot. One updated value invalidates every entry after it, so frequent updates mean
O(n)rebuilds — at that point you want a Fenwick tree (a structure beyond this course) or to rethink the approach. Prefix sums shine when the data is read-heavy. - Sums only — not max/min. Subtraction can cancel a prefix of sums, but there is no way to "subtract away" a maximum. Range-max needs different tools.
Quick check
You wrote prefix[r] - prefix[l] instead of prefix[r+1] - prefix[l]. Predict the bug's symptom.
Answer it in the interactive lesson to keep your progress.
How fast is it? (complexity)
Using the vocabulary from the Complexity & Time lesson, the trade is one linear build for constant-time answers:
| Approach for q queries | Time | Space |
|---|---|---|
| re-add each range | O(n · q) | O(1) |
| prefix sums | O(n + q) — build once, subtract per query | O(n) |
Key takeaways:
prefix[i]= total of the firstivalues, with a leading 0.sum(l..r) = prefix[r+1] − prefix[l]— everything before the range cancels.- Preprocess once, answer forever — the pattern behind many "lots of queries" problems.
- Sums only, and only while the data holds still.
The same cancelling idea powers a family of classics, each its own lesson later (no need to know them yet): subarray sum equals K (a running sum plus the hash-table trick — this topic's Level-2 challenge), 2-D prefix sums (rectangle totals in images and grids), and difference arrays (the mirror image: O(1) range updates). Next up in order: Hash Tables — the instant-lookup tool that pairs with running sums.