Prefix Sum & Difference Arrays
Why prefix sum exists — the story
You built a dashboard for a stock trading desk. Traders keep asking the same question in different forms: "How much revenue did we book between March 3rd and March 17th?" "What's the total volume from tick 200 to tick 800?" Every question is a range sum over the same underlying array.
The obvious answer: sum the range. A for loop from l to r, accumulate, return. It's five lines. For one query on 1,000 elements it's instant. For a hundred queries it's a hundred loops — still fine.
But the desk sends 50,000 queries per second and the array has 10⁶ elements. Now every query averages 5·10⁵ operations; total workload is 2.5·10¹⁰ per second. The CPU has 10⁹ cycles per second. You are 25× slower than realtime. Traders are getting stale numbers; the manager is asking questions in Slack. Every query is redoing work — array element a[500] gets added into every range that includes it, over and over.
The pattern is to trade one-time prep for permanently cheap queries. Compute a running total array pre[] once: pre[i] = sum of everything strictly before index i. Now every range sum becomes one subtraction: sum(l..r) = pre[r+1] - pre[l]. O(n) prep + O(1) per query. For the trading desk: prep once (10⁶ ops), then every query is a single subtraction — the CPU handles 50K queries per second with time to spare.
The mirror image — the difference array — makes range updates cheap: instead of adding +5 to every element in [l, r], you flag +5 at l and -5 at r+1, then run a prefix sum at the end to materialize the final array. Range-update problems that would be O(nQ) become O(n + Q).
And the party trick: pair prefix sums with a hash map to count subarrays with a target sum — even with negative numbers, where a sliding window silently fails. That's the pattern behind Subarray Sum Equals K, one of the top-10 most-asked LeetCode problems in FAANG interviews.
The core idea — precompute once, query in O(1) forever
Prefix Sum — one subtraction answers any range
Drag the sliders to pick a range [l, r]. Watch how pre[r+1] − pre[l] collapses to O(1).
a = 3 1 4 1 5
pre = 0 3 4 8 9 14 pre[i] = sum of a[0..i-1]
sum(l..r) = pre[r+1] - pre[l] e.g. sum(1..3)=pre[4]-pre[1]=9-3=6Read that carefully. pre[] has length n+1, not n. The extra slot at pre[0] = 0 is not a mistake — it lets you query sum(0..r) = pre[r+1] - pre[0] without special-casing the left edge. Every off-by-one bug in prefix sum comes from getting pre[]'s length wrong.
"Sum over a range" ⇒ prefix sums. "Count subarrays whose sum = k" ⇒ prefix sums as keys in a hash map: a subarray (l,r] has sum k iff pre[r]-pre[l]=k, i.e. pre[l]=pre[r]-k was seen before.
When to use it — recognition signals
Reach for prefix sum (or its variants) when:
- Many range-sum queries on a static array — build once, answer each in O(1).
- Count subarrays with sum = k (or divisible by k, or in a range) — combine prefix sum with a HashMap of
pre -> count. - Range updates on an array followed by a materialization pass — difference array turns O(nQ) into O(n+Q). Classic examples: Corporate Flight Bookings, Car Pooling, Range Addition.
- 2D range-sum queries — extend to 2D prefix sum (a.k.a. summed-area tables). Answers rectangle-sum queries in O(1) with O(nm) prep. Used by image-processing algorithms.
- Contiguous subarray with equal 0s and 1s — remap
0 → -1, then a subarray sums to 0 iffpre[l] == pre[r]. This is the equal-partition trick. - Sliding window doesn't work because values can be negative — a window can't reliably shrink when the sum can go up or down. Prefix sums + hashing is the escape hatch.
When NOT to use it
- You need range operations other than sum — prefix sum extends to prefix-max only for immutable arrays; prefix-min/max with updates is a segment tree, not prefix sum.
- The array is dynamic (values change between queries) — prefix sum recomputes from scratch after every update. If you have thousands of updates interleaved with queries, use a Fenwick tree (BIT) or segment tree for O(log n) both.
- Just one query on the whole array — prefix sum's prep cost equals the query cost. Just accumulate in a single loop.
- Multi-dimensional ranges beyond 2D — 3D prefix sum works but memory is O(nmp) and inclusion-exclusion has 8 terms. Consider whether the problem really needs that dimensionality.
- The subarray-sum target is 0 and the array is all zeros — degenerate case; the count blows up quadratically. Handle explicitly.
The templates
Template 1: 1D prefix sum for range queries
class RangeSumQuery {
int[] pre; // length n+1; pre[0]=0
RangeSumQuery(int[] a) {
pre = new int[a.length + 1];
for (int i = 0; i < a.length; i++) {
pre[i + 1] = pre[i] + a[i]; // running total
}
}
int sum(int l, int r) { // inclusive [l, r]
return pre[r + 1] - pre[l]; // O(1) per query
}
}Invariant: pre[i] equals a[0] + a[1] + ... + a[i-1]. Length is n+1. pre[0] = 0 is the sum of the empty prefix. Complexity: O(n) build, O(1) per query, O(n) space.
Template 2: Subarray Sum Equals K (the hash-map trick)
int subarraySumEqualsK(int[] a, int k) {
Map<Integer, Integer> countByPrefix = new HashMap<>();
countByPrefix.put(0, 1); // empty prefix has sum 0, seen once
int running = 0, answer = 0;
for (int x : a) {
running += x;
// Any earlier position with prefix (running - k) gives a subarray summing to k.
answer += countByPrefix.getOrDefault(running - k, 0);
countByPrefix.merge(running, 1, Integer::sum);
}
return answer;
}Invariant: at every iteration, countByPrefix holds the number of times each prefix sum has appeared up to and including the current position. Complexity: O(n) time, O(n) space. Handles negative numbers — the killer feature vs. sliding window.
The put(0, 1) line matters. It represents the "empty prefix": if the running total ever equals k itself, that's a valid subarray starting at index 0. Forgetting this line makes the code silently return answer - 1 for those cases.
Template 3: Difference array for range updates
int[] applyRangeUpdates(int n, int[][] updates) { // updates[i] = [l, r, delta]
int[] diff = new int[n + 1];
for (int[] u : updates) {
diff[u[0]] += u[2]; // start of range
diff[u[1] + 1] -= u[2]; // one past end
}
int[] result = new int[n];
result[0] = diff[0];
for (int i = 1; i < n; i++) {
result[i] = result[i - 1] + diff[i]; // prefix sum reveals final values
}
return result;
}Invariant: at the end, result[i] equals the sum of delta values from all updates whose range contains i. Complexity: O(n + Q). Compare to naive: O(nQ).
Template 4: 2D prefix sum (summed-area table)
class RangeSum2D {
int[][] pre;
RangeSum2D(int[][] m) {
int r = m.length, c = m[0].length;
pre = new int[r + 1][c + 1];
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++)
pre[i+1][j+1] = m[i][j] + pre[i][j+1] + pre[i+1][j] - pre[i][j];
}
int rectSum(int r1, int c1, int r2, int c2) { // inclusive rectangle
return pre[r2+1][c2+1] - pre[r1][c2+1] - pre[r2+1][c1] + pre[r1][c1];
}
}Invariant: pre[i][j] = sum of the sub-rectangle from (0,0) to (i-1, j-1). Complexity: O(rc) build, O(1) per query. Trap: the inclusion-exclusion in rectSum has four terms — miss a sign and you get random wrong answers.
Complexity summary
| Approach | Build | Query | Update | Space |
|---|---|---|---|---|
| Naive range sum | 0 | O(n) | O(1) | O(n) |
| 1D prefix sum | O(n) | O(1) | O(n) rebuild | O(n) |
| Fenwick tree | O(n log n) | O(log n) | O(log n) | O(n) |
| Segment tree | O(n) | O(log n) | O(log n) | O(n) |
| 2D prefix sum | O(rc) | O(1) | O(rc) rebuild | O(rc) |
| Difference array | O(n+Q) | O(1) after materialize | O(1) | O(n) |
Rule of thumb: prefix sum when array is static; Fenwick/segment tree when updates are frequent.
Traps & gotchas — the 5 that fail candidates on interview day
The most common bug in this pattern. pre[] must have length n+1, with pre[0] = 0. If you allocate pre[n], you have no pre[0] sentinel and must special-case queries starting at index 0. Rule: always size pre[] to n+1.
This entry represents the empty prefix. Without it, subarrays that start at index 0 are undercounted. On input [3, 4] with k = 3, you should return 1 but return 0. Rule: seed the hash with {0: 1} before the loop.
pre[i] for n = 10⁵ values of 10⁹ reaches 10¹⁴ — well outside int. Use long[]. This is the same bug class as Bloch's overflow in binary search: silent, sometimes returns negative garbage. Rule: if Σa[i] might exceed 2·10⁹, prefix sums must be long.
For diff[r+1] where r == n-1, r+1 == n — you must allocate diff of size n+1, not n. Off-by-one array-out-of-bounds is a runtime crash the interviewer sees clearly.
Prefix sums are a snapshot. If you modify a[] after building pre[], every subsequent query returns stale data. In a follow-up "now support point updates" question, migrate to a Fenwick tree instead of hoping to patch pre[] in place.
History — Blelloch's parallel prefix, 1990
The prefix-sum operation was formalized by Guy Blelloch at CMU in his 1990 paper "Prefix Sums and Their Applications." The paper proved that prefix sum — despite looking inherently sequential — could be parallelized to O(log n) depth using n processors via a "work-efficient" tree-reduction pattern. That algorithm became the foundation of CUDA's thrust::inclusive_scan and every modern GPU primitive for reductions, sorting, and histogram-building.
Every time you git diff and see a fast enumeration of changed lines, or your ML framework runs an argmax reduction across 10⁴ GPU cores, you're seeing Blelloch's algorithm in action. In interviews, dropping the phrase "the parallel-prefix-scan variant" signals depth beyond LeetCode.
The difference-array trick appears informally in Knuth's Art of Computer Programming Vol 1 (1968), but the modern interview form — turning Q range updates into a single O(n) pass — was popularized on TopCoder and Codeforces in the mid-2000s.
Canonical problem walkthrough — Subarray Sum Equals K
Problem (↗ LeetCode): Given an integer array nums and integer k, return the number of contiguous subarrays whose sum equals k. Values can be negative.
Approach 1 — Brute force
Two nested loops. For each start i, extend to each j ≥ i and check if the sum equals k.
int subarraySumBrute(int[] nums, int k) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
int sum = 0;
for (int j = i; j < nums.length; j++) {
sum += nums[j];
if (sum == k) count++;
}
}
return count;
}Complexity: O(n²) time, O(1) space. For n = 2·10⁴, that's 4·10⁸ operations — tight but might squeak by LeetCode's 2-second limit. Interviewer smiles thinly.
Approach 2 — Prefix sums with linear scan for pair search
Build pre[], then for each r, scan all l ≤ r looking for pre[l] == pre[r+1] - k.
int subarraySumTwoLoop(int[] nums, int k) {
int n = nums.length;
long[] pre = new long[n + 1];
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];
int count = 0;
for (int r = 0; r < n; r++)
for (int l = 0; l <= r; l++)
if (pre[r + 1] - pre[l] == k) count++;
return count;
}Complexity: still O(n²), but the inner check is O(1) instead of accumulating a fresh sum. Slightly faster constant factor. Not the point — this is a stepping stone showing you've identified prefix sum but haven't yet hashed.
Approach 3 — Prefix sums with hash map (the interview answer)
The key insight: for each new position r, we want to count how many earlier prefixes pre[l] satisfy pre[l] == pre[r+1] - k. That's a lookup, not a scan — so use a HashMap.
int subarraySum(int[] nums, int k) {
Map<Long, Integer> seen = new HashMap<>();
seen.put(0L, 1); // empty prefix — one occurrence of "sum 0 so far"
long running = 0;
int count = 0;
for (int x : nums) {
running += x;
count += seen.getOrDefault(running - k, 0); // how many earlier prefixes complete a k-subarray?
seen.merge(running, 1, Integer::sum); // record the current prefix
}
return count;
}Complexity: O(n) time (one pass, O(1) hash ops), O(n) space (worst-case, every prefix distinct).
Interview commentary:
- "Brute force is O(n²). I can do better."
- "For each index r, a subarray ending at r has sum k iff
pre[r+1] - pre[l] = kfor some earlierl. That meanspre[l] = pre[r+1] - k." - "So keep a HashMap of prefix sums seen so far. At each r, look up how many earlier positions had the required prefix value."
- "O(n) time and space. The
put(0, 1)handles the case where a subarray from index 0 sums to k."
Complexity ladder
| Approach | Time | Space | When |
|---|---|---|---|
| Brute force | O(n²) | O(1) | Reference / very small n |
| Prefix + scan | O(n²) | O(n) | Stepping stone during whiteboard |
| Prefix + HashMap | O(n) | O(n) | Interview default |
Recognize by
- many range-sum queries over a static array — precompute pre[], each query is O(1)
- "count subarrays with sum k" (with hash map, works for negative values too)
- "range-update, point-query" — the difference-array mirror
When NOT to use it
You need to update array values and query ranges in the same run — a plain prefix sum is O(1) query but O(n) update. For both operations in O(log n), reach for Fenwick / segment tree.
Subarray Sum Equals K Medium
↗ LeetCode: Subarray Sum Equals K
prefix - k has appeared.Problem
Count how many contiguous subarrays sum exactly to k. The array may contain negative numbers — which is what rules out a sliding window.
Constraints: 1 ≤ n ≤ 2·10⁴; values and k fit in int; negatives allowed.
Example 1: nums = [1,2,1,2,1], k = 3 → 4.
Example 2: nums = [1,-1,0], k = 0 → 3 ([1,-1], [1,-1,0], and [0]).
Solution — brute force
Start with the direct baseline: enumerate every candidate and compute the answer from scratch. It is correct, but it repeats the exact work that the pattern is meant to reuse.
int subarraySumBrute(int[] a, int k) {
int ans = 0;
for (int left = 0; left < a.length; left++) {
int sum = 0;
for (int right = left; right < a.length; right++) {
sum += a[right];
if (sum == k) ans++;
}
}
return ans;
}Brute-force cost: O(n²) time, O(1) space — too slow for n ≥ 10⁴.
Solution — optimized
The optimized idea counts prefix pairs. At running prefix pre, every earlier prefix equal to pre - k forms a subarray ending here with sum k, so a frequency map gives the answer immediately.
Pattern. Prefix sum + hash map of prefix frequencies. Handles negatives (sliding window cannot).
Java.
int subarraySum(int[] a, int k) {
Map<Long,Integer> count = new HashMap<>();
count.put(0L, 1); // empty prefix
long pre = 0; int ans = 0;
for (int x : a) {
pre += x;
ans += count.getOrDefault(pre - k, 0);
count.merge(pre, 1, Integer::sum);
}
return ans;
}Time Complexity
Existing summary: Time O(n) · Space O(n).
The scan is O(n) because each array value updates one running prefix and performs two expected-O(1) hash-map operations.
Space Complexity
Space is O(n) in the worst case because every prefix sum can be distinct and stored in the map.
Learning notes
- Why
Map<Long,Integer>? — prefix sums can exceed int range. - Why
count.put(0L, 1)? — it represents the empty prefix before index 0. - Why add
count.getOrDefault(pre - k, 0)? — those prior prefixes make subarrays summing to k. - Why merge
preafter counting? — the current prefix should be available only to future endings. - Why frequencies, not one index? — multiple prior prefixes can create multiple valid subarrays.
count maps each prefix-sum value to how many indices produced it among the processed prefix. At index r, the number of valid l is count[pre - k].
a=[1,2,1,2,1], k=3. Running prefixes 0,1,3,4,6,7. Each time pre−3 was seen before, you found a subarray: pairs give [1,2],[2,1],[1,2],[2,1] → 4.
Forgetting the count.put(0,1) seed drops subarrays that start at index 0. Do not use a sliding window here — negatives destroy the monotonic shrink.
The shared idea is charge a subarray-with-a-target-property to its prefix: a subarray (l,r] has the property iff two prefixes differ by the target, so you store seen prefixes in a map. Recognize it in Contiguous Array (map a 0/1 array's ±1 running sum to the first index it appeared — a balanced subarray means equal prefixes) and Subarray Sums Divisible by K (bucket prefixes by pre mod k; two prefixes in the same bucket bound a divisible subarray). The transfer trick: rephrase "count subarrays where X" as "count prefix pairs that differ by X."
Same pattern, new tweaks
| Variation | The one thing that changes | Time |
|---|---|---|
| Subarray Sums Divisible by K | key the map on pre mod k instead of the raw prefix | — |
| Contiguous Array (equal 0s and 1s) | treat 0 as −1; a subarray is balanced when two prefixes are equal | — |
| Continuous Subarray Sum (multiple of k) | same mod k bucketing, but store the earliest index to enforce a length ≥ 2 | — |
| Binary Subarrays With Sum | count prefixes equal to pre − goal | — |
Difference Array (Range Update) Medium
↗ LeetCode: Corporate Flight Bookings
Problem
You're given many range updates — each adds v to every element in [l, r] — and you only need the final array after all updates. Do it in O(n + m), not O(n·m).
Constraints: n slots, m updates, each 1 ≤ l ≤ r ≤ n; running totals can exceed int → use long.
Example 1: n = 5, bookings [1,2,10], [2,3,20], [2,5,25] → [10,55,45,25,25].
Example 2: n = 3, bookings [1,1,5] → [5,0,0] (single-point range closes immediately after index 0).
Solution — brute force
Start with the direct baseline: enumerate every candidate and compute the answer from scratch. It is correct, but it repeats the exact work that the pattern is meant to reuse.
int[] corpFlightBookingsBrute(int[][] bookings, int n) {
int[] res = new int[n];
for (int[] b : bookings)
for (int i = b[0] - 1; i <= b[1] - 1; i++) res[i] += b[2];
return res;
}Brute-force cost: O(n·m) time, O(n) output space — too slow when both flights and bookings are large.
Solution — optimized
A range add can be represented by two endpoint marks: start adding at l, stop adding after r. One final prefix pass turns those marks into the actual per-index totals.
Pattern. Invert prefix sum: to add v to [l, r], do diff[l] += v; diff[r+1] -= v. One final prefix sum materializes all updates.
Java.
// Corporate Flight Bookings: bookings[i] = {first, last, seats} (1-indexed)
int[] corpFlightBookings(int[][] bookings, int n) {
long[] diff = new long[n + 1];
for (int[] b : bookings) {
diff[b[0] - 1] += b[2];
diff[b[1]] -= b[2];
}
int[] res = new int[n];
long run = 0;
for (int i = 0; i < n; i++) { run += diff[i]; res[i] = (int) run; }
return res;
}Time Complexity
Existing summary: Time O(n + m) · Space O(n).
Processing m bookings is O(m) because each update writes two diff cells; reconstructing n flights is O(n), so total time is O(n + m).
Space Complexity
Space is O(n) for the difference array and output array. The extra +1 slot is a boundary sentinel for closing ranges at the end.
Learning notes
- Why
long[] diff? — many bookings can accumulate beyond int during reconstruction. - Why
b[0] - 1? — bookings are 1-indexed, Java arrays are 0-indexed. - Why
diff[b[1]] -= b[2]? —b[1]is the first index after the inclusive range. - Why length
n + 1? — ranges ending at flight n need a safe closing decrement. - Why one prefix pass? — the running sum materializes all active increments.
Batch many range increments in O(1) each, then reconstruct in O(n). Ideal when all updates precede all queries.
After processing, prefix(diff)[i] equals the net of all increments covering index i.
n=5, bookings [1,2,10],[2,3,20],[2,5,25]. Endpoint marks then one prefix pass → per-flight seats [10,55,45,25,25] — three range adds settled in one sweep.
Off-by-one at r+1; size the array n+1 so the closing decrement never overflows the bounds.
2D difference arrays handle sub-rectangle increments; combined with a 2D prefix sum they answer Range Sum Query 2D in O(1) per query.
Same pattern, new tweaks
"Mark the endpoints of each range, then one prefix pass materializes all updates" scales across dimensions:
| Variation | The one thing that changes | Time |
|---|---|---|
| Corporate Flight Bookings | +seats at first, −seats after last; one sweep gives per-flight totals | — |
| Car Pooling | a difference array over the timeline of pick-ups (+) and drop-offs (−); check capacity never overflows | — |
| Range Addition | the canonical form — apply many [l, r] += v in O(1) each, reconstruct once | O(1) |
| 2D — Range Addition II / stamping a grid | a 2D difference array marks the four corners of each rectangle | — |
2D Prefix Sum (Range Sum Query 2D) Medium
↗ LeetCode: Range Sum Query 2D
Problem
Preprocess an immutable matrix so each query "sum of the sub-rectangle from (r1,c1) to (r2,c2)" answers in O(1).
Constraints: grid up to ~200×200; many queries → build once, then O(1) each.
Example 1: on [[3,1],[2,4]], sumRegion(0,0,1,1) = 10 (the whole grid); sumRegion(1,1,1,1) = 4.
Example 2: on [[5]], sumRegion(0,0,0,0) = 5 (padding handles the smallest rectangle).
Solution — brute force
Start with the direct baseline: enumerate every candidate and compute the answer from scratch. It is correct, but it repeats the exact work that the pattern is meant to reuse.
class NumMatrixBrute {
private final int[][] m;
NumMatrixBrute(int[][] matrix) { m = matrix; }
int sumRegion(int r1, int c1, int r2, int c2) {
int sum = 0;
for (int r = r1; r <= r2; r++)
for (int c = c1; c <= c2; c++) sum += m[r][c];
return sum;
}
}Brute-force cost: O(R·C) per query in the worst case, O(1) extra space — too slow when many queries arrive.
Solution — optimized
The optimized class pays one preprocessing pass to build a padded 2D prefix table. Every query then becomes four table lookups using inclusion–exclusion.
Java.
class NumMatrix {
private final long[][] P;
NumMatrix(int[][] m) {
int R = m.length, C = m[0].length;
P = new long[R + 1][C + 1];
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++)
P[i+1][j+1] = m[i][j] + P[i][j+1] + P[i+1][j] - P[i][j];
}
int sumRegion(int r1, int c1, int r2, int c2) {
return (int)(P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]);
}
}Time: O(RC) build, O(1) query.
Time Complexity
Building P is O(RC) because each matrix cell contributes to one prefix-table cell. Each sumRegion call is O(1) because it reads four precomputed corners.
Space Complexity
Space is O(RC) for the padded prefix table P; the extra top row and left column simplify boundary math.
Learning notes
- Why
long[][] P? — rectangle sums can be larger than one cell value. - Why size
R + 1byC + 1? — padding makes boundary queries safe. - Why write
P[i+1][j+1]? — prefix indices mean sum before this row/col boundary. - Why subtract
P[i][j]while building? — the top-left rectangle was added twice. - Why the query has
- - +terms? — subtract top/left strips, then add back their overlap.
Inclusion–exclusion: sum(r1,c1,r2,c2) = P[r2+1][c2+1] − P[r1][c2+1] − P[r2+1][c1] + P[r1][c1].
m=[[3,1],[2,4]]. The padded prefix table gives sumRegion(0,0,1,1) = P[2][2] − P[0][2] − P[2][0] + P[0][0] = 10 − 0 − 0 + 0 = 10 (the whole grid), and sumRegion(1,1,1,1)=4 (just the corner).
P[i][j] holds the sum of the sub-rectangle from (0,0) to (i-1,j-1); the padding row/column of zeros makes every query boundary-safe.
Sign/index errors in the four-term formula, or omitting the +1 padding — then corner queries read out of bounds. Add back the double-subtracted corner (+ P[r1][c1]).
The +/−/− /+ inclusion–exclusion pattern reappears in Maximal Rectangle accounting and 2D sweep problems.
Same pattern, new tweaks
| Variation | The one thing that changes | Time |
|---|---|---|
| Matrix Block Sum | answer each cell as the sum of a k-radius block using the same four-corner formula | — |
| Count Submatrices With Target Sum | fix a pair of rows, collapse columns to 1D prefix sums, then reuse the "subarray sum = k" hash-map count | — |
| Maximal Square / Maximal Rectangle | combine per-row prefix counts with a histogram/DP to bound the largest all-ones region | — |