Prefix sums
easyprefix[r+1] − prefix[l] cancels the shared head and leaves exactly a[l..r]. One linear pass buys constant-time range sums for every query afterwards.
O(n) buildWorst O(1) per querySpace O(n)Saved in this browser - no sign-up, nothing sent anywhere.
How prefix sums works
prefix[i] holds the sum of the first i elements, so the table is one slot longer than the array and starts with prefix[0] = 0. Building it is a single pass: prefix[i+1] = prefix[i] + a[i]. After that, any inclusive range sum is one subtraction - prefix[r+1] - prefix[l] - because the two entries share the head a[0..l-1] and subtraction cancels it exactly.
The economics are the point. Summing a range directly costs its width, so q queries cost O(n·q) in the worst case; building once and subtracting costs O(n + q). The price is O(n) memory - the standard lookup-table trade. It pays as soon as the same unchanging array faces more than a couple of range questions.
The leading zero earns its slot. Anchoring prefix[0] = 0 means a query starting at index 0 goes through the same formula as every other - no branch, no special case. Most prefix-sum bugs are off-by-ones at the boundaries, and the sentinel removes the whole class for the cost of one integer.
Step by step
- Take a = 3, 7, 2, 9, 4. Allocate six prefix slots and anchor prefix[0] = 0.
- Fill left to right: prefix[1] = 0 + 3 = 3, prefix[2] = 3 + 7 = 10, prefix[3] = 10 + 2 = 12.
- Finish the build: prefix[4] = 12 + 9 = 21 and prefix[5] = 21 + 4 = 25. Five additions, paid once.
- Query sum(1, 3). prefix[4] = 21 counts a[0..3]; prefix[1] = 3 counts just a[0].
- Subtract: 21 - 3 = 18, which is exactly 7 + 2 + 9. Two reads and one subtraction, however wide the range.
- Ask sum(0, 4) next: prefix[5] - prefix[0] = 25 - 0 = 25. Same formula, no edge case - that is the sentinel working.
Complexity
| Best case time | O(n) build |
|---|---|
| Worst case time | O(1) per query |
| Space | O(n) |
Reference implementation
Python
from itertools import accumulate
def build_prefix(a):
"""prefix[i] = sum of the first i elements. Note the leading 0."""
return [0] + list(accumulate(a))
def range_sum(prefix, l, r):
"""Inclusive sum of a[l..r] in O(1)."""
return prefix[r + 1] - prefix[l]JavaScript
function buildPrefix(a) {
const prefix = new Array(a.length + 1).fill(0);
for (let i = 0; i < a.length; i++) prefix[i + 1] = prefix[i] + a[i];
return prefix; // prefix[0] = 0 removes every edge case
}
const rangeSum = (prefix, l, r) => prefix[r + 1] - prefix[l];Worth noticing
Precompute once, answer forever
One O(n) pass buys O(1) range sums for every query afterwards. With q queries the naive approach costs O(n·q); this costs O(n + q). The trade is O(n) extra memory - the same bargain as every lookup table.
The leading zero is not decoration
prefix[0] = 0 means `sum(0, r)` needs no special case. Indexing prefix from 1 is the single most reliable way to avoid off-by-one errors in this pattern.
Subtraction is what makes it work
prefix[r+1] counts everything up to r; prefix[l] counts everything before l. Subtracting cancels the shared head and leaves exactly a[l..r]. The same cancellation extends to 2-D with inclusion-exclusion.
It underpins more than you would think
Subarray-sum-equals-k, count-of-nice-subarrays, and every range-query problem start here. Combine it with a hash map of seen prefix values and a whole class of problems becomes linear.
Common pitfalls
- Sizing prefix at n with no leading zero. Queries starting at index 0 then need a special case, and that branch is where the off-by-ones breed.
- Writing prefix[r] - prefix[l] for the inclusive range a[l..r]. The correct right end is prefix[r+1] - dropping the +1 silently excludes a[r].
- Using it on data that keeps changing. One write to a[i] stales every prefix entry after i; frequent updates want a Fenwick tree, not an O(n) rebuild per change.
- Overflow in fixed-width languages: prefix entries grow toward the sum of the entire array, which can exceed the element type even when every individual value fits.
Where it is used
- Range sum queries on static arrays - the baseline every fancier range structure is measured against.
- Subarray sum equals k: pair the running prefix with a hash map of seen values, and counting becomes one linear pass.
- 2-D prefix tables answer rectangle sums by inclusion-exclusion - image integrals and grid problems.
- Any additive range statistic: counts matching a predicate, weighted sums, averages over ranges.
Frequently asked questions
What are the time and space complexity of prefix sums?
The build is O(n) - one addition per element, once. Every query after that is O(1): two reads and a subtraction, whatever the range width. Space is O(n) for the n + 1 table entries. Against a naive O(n·q) for q queries, the total of O(n + q) is the whole sales pitch.
Why does prefix[r+1] - prefix[l] give the range sum?
prefix[r+1] is the sum of a[0..r]; prefix[l] is the sum of a[0..l-1]. Both include the head a[0..l-1], so subtracting cancels it and leaves a[l] + ... + a[r] exactly. Nothing else survives - that cancellation is the entire mechanism.
Why is the prefix array one element longer than the input?
The extra slot is the sentinel prefix[0] = 0. Without it, a query starting at index 0 has nothing to subtract and needs its own branch. With it, sum(0, r) = prefix[r+1] - prefix[0] flows through the same formula as every other query.
What if the array changes between queries?
One point update invalidates every prefix entry after it. If changes are rare, rebuild in O(n) and keep the O(1) queries. If updates and queries interleave heavily, switch to a Fenwick tree - O(log n) for both operations - or a segment tree for richer range maths.