A reporting endpoint stores yesterday’s hourly revenue in a long[] — 24 slots, or 8,760 if finance keeps a year of days. Callers ask sum(l, r): revenue from hour l through hour r. After midnight the array is frozen. Every request still walks a[l] through a[r] and adds.
At 24 hours that loop is invisible. At a year of days, and a few thousand concurrent reports, you are re-adding the same numbers on every call. The hours already sit in a contiguous array; index i is free. The procedure is the bill: a linear scan of a slice that never changes.
A prefix array turns a range sum into two lookups after one O(n) precompute. You pay the scan once. After that, sum(l, r) is subtraction. This post is that procedure: exclusive versus inclusive prefixes, a walked example, a Java long[], a short 2D sketch, difference arrays when you need range writes before a freeze, and when a Fenwick or segment tree is the next bill. The Algorithms Roadmap owns the glossary this series will not re-teach.
The loop you are paying twice
The naive handler is honest and expensive:
long sumRange(long[] a, int l, int r) {
long s = 0;
for (int i = l; i <= r; i++) {
s += a[i];
}
return s;
}Correct. Cost O(r - l + 1) per request. If the hot path is “same array, many ranges,” you pay the same additions again and again. Prefix sums exist for that job: offline, static array, range sum — or any aggregate you can undo.
Note: Undo means an inverse. Sum has subtraction. XOR has XOR. Min, max, and gcd do not: knowing the min of [0..r] and of [0..l-1] does not give you the min of [l..r]. A prefix of mins answers “min so far,” not an interior slice. The freeze is the invariant: you see the whole day before the first query.
Pick a convention: exclusive prefix
Two common layouts. Mixing them is how off-by-one bugs ship.
Exclusive (this post’s default): prefix[0] = 0, and prefix[i] is the sum of the first i elements — a[0] + … + a[i-1]. The prefix is one longer than a. Inclusive range [l, r] (both ends in the array) is:
sum(l, r) = prefix[r + 1] - prefix[l]No special case when l == 0. prefix[l] is everything strictly before index l. prefix[r + 1] is everything through index r. Subtract. Half-open [l, r) on the same table is prefix[r] - prefix[l]. Write which contract you mean.
Inclusive: prefix[i] = a[0] + … + a[i]. Length matches a. Then:
sum(l, r) = prefix[r] - prefix[l - 1]You must treat l == 0 as “subtract nothing,” or shift to 1-based indexing with a dummy prefix[0] = 0. Fenwick trees often use that 1-based inclusive shape. This post stays 0-based exclusive so the Java sketch matches a[i] with no sentinel in the source array.
Pick one convention and write the formula next to the array. Mixing prefix[r] - prefix[l] with an exclusive table (or prefix[r + 1] - prefix[l] with an inclusive one) looks like a missed first hour, and it will pass a test that only queries l = 0.
A walked example
Revenue by hour, five slots:
index: 0 1 2 3 4
a: 4 2 7 1 5Build exclusive prefixes left to right. Each slot is the previous prefix plus the element that just ended:
prefix[0] = 0
prefix[1] = 0 + 4 = 4 // first 1 element (a[0])
prefix[2] = 4 + 2 = 6 // first 2 (a[0]..a[1])
prefix[3] = 6 + 7 = 13
prefix[4] = 13 + 1 = 14
prefix[5] = 14 + 5 = 19 // whole arrayQuery hours 1 through 3 (values 2, 7, 1):
sum(1, 3) = prefix[4] - prefix[1]
= 14 - 4
= 10
check: 2 + 7 + 1 = 10prefix[4] is everything through index 3. prefix[1] is everything before index 1. The slice in between is exactly [1, 3]. Hours 0 through 4 is prefix[5] - prefix[0] = 19 — no branch for l == 0. A single cell, hour 2, is prefix[3] - prefix[2] = 13 - 6 = 7. Empty ranges are outside this contract: inclusive l..r requires l <= r.
Java: build long[] prefix
One pass, then two reads. Use long even when a is int[]: a year’s daily counts in int can overflow the running total long before a single cell does.
static long[] buildPrefix(int[] a) {
long[] prefix = new long[a.length + 1];
for (int i = 0; i < a.length; i++) {
prefix[i + 1] = prefix[i] + a[i];
}
return prefix;
}
static long sum(long[] prefix, int l, int r) {
return prefix[r + 1] - prefix[l];
}buildPrefix is O(n). Each sum is O(1): two array reads and a subtract. Bounds are your problem — 0 <= l <= r < n, where n is prefix.length - 1. Freeze the day, build once, then sum(prefix, l, r) per request.
Note: Java int addition wraps. A prefix of int is a silent overflow on any realistic metrics or revenue series. long[] prefix is the default. If even long is tight, you need BigInteger or a different model — not a tighter loop.
Keep a if callers ask for a single hour by index. The prefix is extra O(n) space, not a replacement unless every read is a range (or a point answered as sum(i, i)).
2D prefix: one rectangle from four corners
A grid of daily revenue by region (rows) and day (columns) has the same job in two dimensions: sum of a sub-rectangle. A 2D prefix is one O(rows * cols) fill, then O(1) per rectangle.
Let S[r][c] be the sum from (0, 0) to (r, c) inclusive — easier to draw than exclusive. Fill with the cell, plus the rectangle above, plus the rectangle to the left, minus the overlap you counted twice:
S[r][c] = a[r][c]
+ S[r - 1][c]
+ S[r][c - 1]
- S[r - 1][c - 1]Treat S[-1][*] and S[*][-1] as 0, or allocate (rows + 1) × (cols + 1) and shift so row 0 and column 0 stay zero. The sum of inclusive rectangle (r1, c1) through (r2, c2) is four corners:
sum = S[r2][c2]
- S[r1 - 1][c2]
- S[r2][c1 - 1]
+ S[r1 - 1][c1 - 1]Subtract the strip above and the strip to the left, then add back the top-left block you subtracted twice. That is inclusion-exclusion, not a new algorithm.
A 3×3 walk:
a: S (inclusive):
1 2 3 1 3 6
4 5 6 5 12 21
7 8 9 12 27 45
sum of middle 2×2 (rows 1..2, cols 1..2):
5+6+8+9 = 28
S[2][2] - S[0][2] - S[2][0] + S[0][0]
= 45 - 6 - 12 + 1 = 28Keep this as a sketch. Use long[][] for the same overflow reason. If a cell mutates, every S that includes it is stale — rebuild is O(rows * cols), fine after a nightly load, not on every click.
Difference array: range updates, then one rebuild
Prefix sums answer range reads on a frozen array. The dual job is range writes you will freeze afterward: add v to every index in [l, r], many times, then read the result (or build a prefix for later range reads).
A difference array stores consecutive deltas: diff[0] = a[0], diff[i] = a[i] - a[i - 1] for i > 0. Reconstructing a is a prefix sum of diff. Adding v to [l, r] is two writes:
diff[l] += v
diff[r + 1] -= v // omit if r is the last indexYou do not touch the interior. After all updates, one prefix rebuild restores a — O(1) per add, O(n) once to restore.
static void addRange(long[] diff, int l, int r, long v) {
diff[l] += v;
if (r + 1 < diff.length) {
diff[r + 1] -= v;
}
}
static long[] restore(long[] diff) {
long[] a = new long[diff.length];
a[0] = diff[0];
for (int i = 1; i < diff.length; i++) {
a[i] = a[i - 1] + diff[i];
}
return a;
}Walk: start from zeros, length 5. Add 3 to [1, 3], then add 1 to [0, 4]:
diff after +3 on [1,3]: [0, 3, 0, 0, -3]
(r+1 = 4 gets -3)
diff after +1 on [0,4]: [1, 3, 0, 0, -3]
(r is last index; no trailing -=)
restore:
a[0] = 1
a[1] = 1 + 3 = 4
a[2] = 4 + 0 = 4
a[3] = 4 + 0 = 4
a[4] = 4 + (-3) = 1
check: [1, 4, 4, 4, 1]That is the right bill when updates are batched and queries come after the freeze — add 10 to every day in March, then a report. It is the wrong bill if a caller needs a[i] after every add.
Do not query mid-stream without rebuilding. The difference array is a write buffer, not a query structure. After restore, buildPrefix on a answers range sums in O(1). Two prefixes, two jobs: difference for batched writes, prefix for batched reads.
When the array mutates on the hot path
If a[i] changes between queries — a live counter, a late correction — rebuilding prefix on every write is O(n) per mutation. You are back to paying a scan. The O(1) query was bought with a lie about the writes.
That job is a different layout. This post does not re-teach those trees:
- Point update plus prefix (or range via two prefixes): Fenwick tree —
O(log n)update and query, one array, least-significant-bit jumps. Inverse required (sum, XOR). - Arbitrary range of an aggregate that may not invert (min, max, gcd), with point updates: segment tree — interval nodes,
O(log n)both ways.
The trigger is one sentence: the array is not frozen. Static prefix if it is. Fenwick or segment tree if it is not. Difference array if the mutations are range adds you can batch before anyone reads.
Complexity
| Operation | Time | Extra space |
|---|---|---|
| Build prefix | O(n) | O(n) for prefix |
| Range sum query | O(1) | — |
| Rebuild after a point write | O(n) | — |
| Difference: one range add | O(1) | O(n) for diff |
Difference: restore a | O(n) | O(n) if you materialize |
Build once, then queries are two lookups. Extra space is n + 1 longs (exclusive). 2D is O(rows * cols) to build and store, O(1) per rectangle.
Name the hot job, as the Algorithms Roadmap said. Range sum on a static array is the cheap column. “Update then query, update then query” pays the rebuild row.
When not to use prefix sums
Skip a prefix array when:
- The array mutates on the query path — you will rebuild
O(n)per write. Use a Fenwick or a segment tree. - The aggregate is not invertible — range min, max, or gcd is not
prefix[r + 1] - prefix[l]. A prefix of mins answersmin(a[0]..a[i]), not an interior[l, r]. - You answer each range once on a throwaway array — the precompute is another
O(n)pass. A single scan of[l, r]can be cheaper when there is no reuse. - n is tiny and the loop is not hot — 24 hours, one report, no prefix.
A static histogram, a frozen daily series, a 2D grid that loads once — those are prefix jobs. A live per-minute counter with a rolling chart is not.
Cheat sheet
Job: range sum on a frozen array (many queries)
Build: prefix[0]=0; prefix[i+1]=prefix[i]+a[i] O(n)
Query: sum(l,r) = prefix[r+1] - prefix[l] O(1)
Space: O(n) extra longs
Inclusive: prefix[i]=sum a[0..i]; sum=prefix[r]-prefix[l-1]
2D: four corners; add back the double-subtracted block
Diff: +v on [l,r] → diff[l]+=v; diff[r+1]-=v; prefix once
Mutates: Fenwick (invertible prefix) or segment tree (any range op)
Overflow: long[] prefix, not int[]Do:
- Freeze, precompute, then answer ranges with two lookups.
- Write the
sum(l, r)formula next to the convention you picked. - Use a difference array when range adds are batched before any read.
Don’t:
- Mix exclusive
prefix[r + 1] - prefix[l]with an inclusive table. - Rebuild the prefix on every point update and call it O(1) queries.
- Subtract prefix mins (or gcds) and expect a range min (or gcd).
Wrap-up
Prefix sums are a procedure on a static array: one O(n) pass, then range sum as subtraction. Exclusive prefixes make sum(l, r) = prefix[r + 1] - prefix[l] with no l == 0 branch; inclusive prefixes are the same idea with a different index. 2D is four-corner inclusion-exclusion. Difference arrays flip the job to batched range writes and one rebuild.
When the cells keep moving, pick a Fenwick or a segment tree. When they do not, stop looping [l, r] on every request.