What is a prefix sum?
A prefix sum is an extra array of running totals built from your data once, so that the sum of any range can be answered with a single subtraction instead of a fresh walk. Entry
prefix[i] holds the total of the first i values, with a 0 parked at the front (the sum of nothing).In this lesson you'll learn how to build the running-total array in one pass, the one-line subtraction that answers any range, and the off-by-one that catches almost everyone.
Where it matters: 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 most of those walks re-add the same numbers the last question just added. The running totals for that data: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.Here's the whole trick in words. Walk the six days once, writing a running total after each: 7, then 10, then 19, 23, 35, 41 — with a 0 up front for "nothing yet". Now "total for days 3 to 5?" is just: the total through day 5 (35) minus everything before day 3 (10) → 25. No re-adding, ever again. Watch the totals being written below, then the subtraction. (The coded build & query lives in the See it step.)
This section has a step-by-step animation in the interactive lesson.
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.(The See it step animates both phases — the table filling up, then the two entries cancelling.)
Build and Query in JavaScript
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.