Why does a prefix-sum array answer range sums in O(1), and why is it sized n+1?
answer
- Stop re-adding the same numbers
- Store totals, not values
- Longer prefix minus unwanted head
- One extra slot holding zero
- P[r+1] - P[l], build O(n)
basics
~20 sA prefix array stores running cumulative totals, so any range sum becomes one subtraction: the total over positions l..r equals P[r+1] - P[l]. The extra leading slot holds 0, so ranges that begin at index 0 need no special case.
solid answer
~40 sBuild once, query forever. Walk the daily-spend values left to right accumulating totals into `P`, where `P[k]` is the sum of the first `k` days; that is a single O(n) pass. Because every prefix total is stored, the spend on days `l..r` inclusive is `P[r+1] - P[l]` — the longer prefix minus the part you do not want — which is O(1) with no loop. The convention that makes this clean is an array of length `n+1` with `P[0] = 0`, representing the empty prefix; without it, a query starting at day 0 has to be special-cased. The trick works because addition has an inverse, so the shared prefix cancels exactly. Total: O(n) time and O(n) extra memory to build, O(1) per query.
code
pseudocode · 12 lines// spend[0..n-1] holds one signed total per day
P = array of length n + 1
P[0] = 0
for i in 0..n-1:
P[i+1] = P[i] + spend[i]
// total spend for days l..r, r included
answer = P[r+1] - P[l]
// days 0..2 -> P[3] - P[0]
// day 4 alone -> P[5] - P[4]
// all n days -> P[n] - P[0]go deeper
Be ready to produce the build loop and the query formula from memory and to say which endpoint is inclusive. This is a warm-up: interviewers use it to check you can set up an index convention before handing you a harder subarray problem.
Explain why the leading zero slot removes the special case at index 0, and state the O(n) build plus O(1) query split without hedging. Be able to justify why the shared prefix cancels rather than just quoting the formula.
Show the habits that keep this correct in production: pin the inclusive-versus-exclusive convention at the API boundary, size the accumulator for the whole horizon, and test the range that starts at 0. A silent off-by-one here reports wrong money, it does not crash.
Own whether a precomputed snapshot belongs in the read path at all — who rebuilds it, how stale a report may be, and what an extra O(n) copy per dataset costs across a fleet. The formula is trivial; the ownership of the derived data is the real decision.
## The problem You have a ledger of per-day expense totals in signed cents — refunds are negative — and a reporting screen keeps asking questions like "what did we spend from day 12 through day 40?" Answering each one by looping over the range costs O(r - l + 1), so q queries over a window of size up to n cost O(n·q). When the ledger is static and the queries are many, that is the wrong shape of cost: you are re-adding the same numbers over and over. ## The construction A prefix-sum array trades one linear pass and O(n) memory for constant-time queries. Define - `P[0] = 0` - `P[k] = a[0] + a[1] + ... + a[k-1]` for k from 1 to n so `P[k]` is "the total of the first k values", and `P` has n+1 slots. Building it is one loop: `P[i+1] = P[i] + a[i]`. Each step is one addition, so the build is O(n) time — not O(n log n), and not O(n²); nothing is re-scanned. ## Why the query is exact The sum over the inclusive range l..r is `P[r+1] - P[l]`. Read it as: everything up to and including position r, minus everything strictly before position l. The overlap — the first l values — appears in both totals and cancels. That cancellation is the whole trick, and it depends on addition having an inverse (subtraction). Any operation with that property supports the same move; operations without one do not. Note what is *not* required. The values need not be sorted, need not be positive, and need not be distinct. Negative entries — refunds — are fine, because subtraction of cumulative totals is exact regardless of sign. This surprises people who first meet prefix sums alongside sliding-window techniques, which often *do* require non-negativity. ## The index convention, and the off-by-one it prevents The n+1 sizing is not decoration. With a length-n array where `P[i]` means "sum through i", the query becomes `P[r] - P[l-1]`, and `l = 0` reads position -1. Every codebase that does this grows a branch like "if l is 0, return P[r]". The leading zero slot makes the empty prefix a real, addressable value, so one formula covers every range including the whole array (`P[n] - P[0]`) and, usefully, the empty range (`P[l] - P[l] = 0`). The second convention to pin down is whether the caller's `r` is inclusive or exclusive. With half-open ranges `[l, r)` the formula is simply `P[r] - P[l]`, which composes more cleanly and is why many range APIs are half-open. Both are correct; mixing them in one code path is the classic bug, and it does not crash — it silently reports the wrong month's spend. ## Costs, side by side | Approach | Preprocess | Per range sum | Extra space | |---|---|---|---| | Scan the range | none | O(r - l + 1) | O(1) | | Prefix array | O(n) | O(1) | O(n) | ## The accumulation trap Prefix totals grow monotonically in magnitude even when the individual values are tiny. A year of daily spend in cents can push past the range of a 32-bit signed accumulator long before any single day does. Runtimes disagree here in a way worth knowing: Python and Ruby promote integers to arbitrary precision so the totals simply keep growing, while Java, Go, C++ and Rust use fixed-width machine words where the accumulator can wrap (or, in some of them, is undefined behaviour on signed overflow). Where arithmetic wraps predictably — modulo 2^k — the *difference* `P[r+1] - P[l]` still comes out right whenever the true range sum fits in the width, because the wraps cancel with the prefixes. That is a fragile thing to rely on and a poor thing to explain in review; widen the accumulator instead. ## When it pays One query: just scan — the build costs as much as the answer. Many queries over data that does not change: the O(n) build amortizes immediately, and the pass is sequential and cache-friendly, so the real speedup usually beats the asymptotic story. Data that changes underneath you is where this structure stops being the right tool.
- The ledger holds three years of signed cents. What breaks in the prefix array before the algorithm does?The accumulator, not the logic. Prefix totals grow monotonically in magnitude even though each day is small, so a fixed-width 32-bit signed slot can overflow around a couple of billion cents while no single day comes close. Use a wider accumulator. In runtimes with predictable wraparound the subtraction still yields the right answer whenever the true range sum fits the width, since the wraps cancel — but that is an accident to avoid depending on, and elsewhere signed overflow traps or is undefined.
- How does the formula change if callers pass ranges with an exclusive right endpoint?It gets simpler: the sum over `[l, r)` is `P[r] - P[l]`, with no +1 anywhere. That is one reason half-open ranges are the common convention — the endpoints compose (adjacent ranges share an index) and the empty range falls out as `P[l] - P[l] = 0`. The danger is not either convention but mixing them: pick one, name it in the signature, and test a range starting at 0 and one ending at n-1.
- Does the trick still work if some days are negative refunds?Yes, without modification. Subtracting cumulative totals is exact for any signed values, because the shared prefix cancels regardless of sign. What negatives do break is the sliding-window family of techniques, which lean on the sum growing as the window widens; people who learn the two patterns together often transfer that non-negativity requirement to prefix sums, where it does not apply.
It is an odometer. To learn how far you drove between two towns you do not re-drive the road; you read the odometer at each town and subtract.
saying these in an interview costs you the question
- Writes the query as P[r] - P[l], off by one
- Claims building the prefix array is O(n log n)
- Says prefix sums require non-negative values
- Thinks the underlying array must be sorted first
- Believes each query still touches every element in the range
- Ignores that cumulative totals overflow before individual values do