When Range Sum Queries Repeat
Imagine you manage a neighborhood library. Daily visitor counts are recorded like [5, 8, 6, 3, 7, 9, 4], and librarians ask "how many came from day 2 to day 5?" dozens of times a day.
If you re-sum from the start for each question, one query costs O(N), so Q queries cost O(N×Q) — far too slow. With a prefix sum, one round of preprocessing lets you answer every query in O(1).
The Core Idea of Prefix Sums
Define the prefix sum array prefix as:
prefix[i] = visitors[0] + visitors[1] + ... + visitors[i-1]So prefix[i] is "the sum of the first i elements." The key trick is to put prefix[0] = 0 (the sum of nothing) at the front. This makes the range-sum formula clean:
sum(l, r) = prefix[r + 1] - prefix[l]Thanks to prefix[0] = 0, ranges with l = 0 work with the exact same formula — no special case.
Walking Through It
For visitors [5, 8, 6, 3, 7, 9, 4], the prefix sums are:
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| prefix | 0 | 5 | 13 | 19 | 22 | 29 | 38 | 42 |
Now the sum of range [2, 5] needs no manual addition:
prefix[6] - prefix[2] = 38 - 13 = 25
Verify: 6 + 3 + 7 + 9 = 25 ✓Range [0, 2] comes out in one step too: prefix[3] - prefix[0] = 19 - 0 = 19.
Why Does Subtraction Work?
prefix[r+1] is the sum from the start through index r, and prefix[l] is the sum from the start through index l-1. Subtracting cancels the front part (0 ~ l-1) exactly, leaving only the l ~ r range you want. Seeing it drawn out makes it click instantly.
Time and Space Complexity
| Complexity | |
|---|---|
| Preprocessing | O(N) |
| Query (single) | O(1) |
| Total (Q queries) | O(N + Q) |
| Space | O(N) |
The more queries you have, the more powerful prefix sums become. For a single query, preprocessing isn't worth it — but when queries repeat over the same array, prefix sums win decisively.
When Should You Use It?
- •When the array is fixed (elements never change) and only range sum queries arrive repeatedly
- •Problems phrased as "sum from l to r" or "repeated subarray sums"
- •If elements change often, consider a segment tree or Fenwick tree instead.
See It in Action on AlgoNote
Watch how the prefix sum array is built and how each range query is answered instantly with a single subtraction, step by step, on AlgoNote.