Prefix Sum Pattern
The Idea
A prefix sum array stores running totals: prefix[i] is the sum of the first i values. Once built (O(n)), the sum of any contiguous range is one subtraction.
steps per day: [3, 8, 2, 7, 4, 6]
index: 0 1 2 3 4 5
prefix: [0, 3, 11, 13, 20, 24, 30]
index: 0 1 2 3 4 5 6
↑
prefix[0] = 0 (sum of nothing) — makes every formula uniform
sum of days 2..4 = prefix[5] − prefix[2] = 24 − 11 = 13 (2 + 7 + 4 ✓)
sum of days 0..2 = prefix[3] − prefix[0] = 13 − 0 = 13
WITHOUT prefix sums: each query loops over the range → O(n) per query WITH prefix sums: O(n) once, then O(1) per query → O(n + q) total
Variation 1: Range Sum Queries
The direct use. Build once, answer many questions.
sum(lo..hi) = prefix[hi + 1] − prefix[lo] Same trick works for anything you can "subtract": counts: how many vowels in s[lo..hi] → prefix count of vowels XOR: XOR of a[lo..hi] → prefixXor[hi+1] ^ prefixXor[lo] products: only if no zeros (division needed) → usually avoid NOT for min / max — they can't be "un-applied". Use a sparse table or a segment tree for range minimum queries.
Variation 2: Count Ranges With a Target Sum (Prefix + Hash Map)
A range lo..hi sums to target
⇔ prefix[hi+1] − prefix[lo] = target
⇔ prefix[lo] = prefix[hi+1] − target
So while scanning, for each new running total R, ask:
"how many earlier prefixes equal R − target?"
A hash map of prefix value → count answers that in O(1).
Daily profit/loss: [4, -2, 3, -1, -3, 5, 2], target 5
running: 0 → 4 → 2 → 5 → 4 → 1 → 6 → 8
↑ seed {0: 1}
at R=5 (after index 2): look for 0 → found 1 → [4, -2, 3]
at R=6 (after index 5): look for 1 → found 1 → [5]
Total: 2 ranges
This is the go-to method for target-sum ranges when values can be negative — where a sliding window fails.
Variation 3: 2D Prefix Sums
P[r][c] = sum of the rectangle from (0,0) to (r−1, c−1)
Build: P[r+1][c+1] = grid[r][c] + P[r][c+1] + P[r+1][c] − P[r][c]
Query: sum(r1,c1 .. r2,c2) =
P[r2+1][c2+1] − P[r1][c2+1] − P[r2+1][c1] + P[r1][c1]
┌─────────────┐
│ A │ B │ wanted = whole − (A+B) − (A+C) + A
│─────┼───────│
│ C │wanted │ A was subtracted twice, so add it back once
└─────────────┘
Variation 4: Difference Arrays (Range Updates)
The reverse direction: many updates to ranges, then read all values once.
Hotel bookings over 6 days: (day lo, day hi, rooms) (0, 2, 3) (1, 4, 2) (3, 5, 1) diff[lo] += rooms; diff[hi + 1] −= rooms diff: [3, 2, 0, -2, 0, -2, -1] prefix → [3, 5, 5, 3, 3, 1] ← rooms booked each day Each update O(1); one final pass O(n).
Code: All Four Variations
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
public class PrefixSum {
// prefix[i] = sum of the first i values (prefix[0] = 0)
static long[] buildPrefix(int[] values) {
long[] prefix = new long[values.length + 1];
for (int i = 0; i < values.length; i++) prefix[i + 1] = prefix[i] + values[i];
return prefix;
}
static long rangeSum(long[] prefix, int lo, int hi) { // inclusive lo..hi
return prefix[hi + 1] - prefix[lo];
}
// Count contiguous stretches summing to target — works with negatives
static int countTargetStretches(int[] values, int target) {
Map<Long, Integer> seen = new HashMap<>();
seen.put(0L, 1); // the empty prefix
long running = 0;
int count = 0;
for (int v : values) {
running += v;
count += seen.getOrDefault(running - target, 0);
seen.merge(running, 1, Integer::sum);
}
return count;
}
// 2D: P[r][c] = sum of the rectangle (0,0)..(r-1,c-1)
static long[][] buildPrefix2D(int[][] grid) {
int rows = grid.length, cols = grid[0].length;
long[][] P = new long[rows + 1][cols + 1];
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++)
P[r + 1][c + 1] = grid[r][c] + P[r][c + 1] + P[r + 1][c] - P[r][c];
return P;
}
static long rectSum(long[][] P, int r1, int c1, int r2, int c2) { // inclusive corners
return P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1];
}
// Difference array: many "add x to days lo..hi" updates, then one pass
static int[] applyBookings(int days, int[][] bookings) {
int[] diff = new int[days + 1];
for (int[] b : bookings) { diff[b[0]] += b[2]; diff[b[1] + 1] -= b[2]; }
int[] out = new int[days];
int running = 0;
for (int d = 0; d < days; d++) { running += diff[d]; out[d] = running; }
return out;
}
public static void main(String[] args) {
long[] prefix = buildPrefix(new int[]{3, 8, 2, 7, 4, 6});
System.out.println("prefix: " + Arrays.toString(prefix));
int[][] queries = {{0, 2}, {2, 4}, {1, 5}};
for (int[] q : queries)
System.out.println("sum of days " + q[0] + ".." + q[1] + ": " + rangeSum(prefix, q[0], q[1]));
int[] pnl = {4, -2, 3, -1, -3, 5, 2};
System.out.println("stretches of " + Arrays.toString(pnl) + " summing to 5: " + countTargetStretches(pnl, 5));
int[][] grid = {{2, 0, 1, 4}, {3, 5, 2, 1}, {1, 2, 6, 3}};
long[][] P = buildPrefix2D(grid);
System.out.println("rect (0,0)-(1,1): " + rectSum(P, 0, 0, 1, 1));
System.out.println("rect (1,1)-(2,3): " + rectSum(P, 1, 1, 2, 3));
int[][] bookings = {{0, 2, 3}, {1, 4, 2}, {3, 5, 1}};
System.out.println("rooms booked per day: " + Arrays.toString(applyBookings(6, bookings)));
}
}Output:
prefix: [0, 3, 11, 13, 20, 24, 30]
sum of days 0..2: 13
sum of days 2..4: 13
sum of days 1..5: 27
stretches of [4, -2, 3, -1, -3, 5, 2] summing to 5: 2
rect (0,0)-(1,1): 10
rect (1,1)-(2,3): 19
rooms booked per day: [3, 5, 5, 3, 3, 1]
Beyond Sums: The General Principle
The hash-map version works for any running quantity where "range value = later − earlier", as long as the question becomes "have I seen a matching earlier value?"
"Ranges with equal numbers of 0s and 1s" → treat 0 as −1; equal counts ⇔ range sum is 0 → longest such range: store the FIRST index of each prefix value "Ranges whose sum is divisible by k" → store prefix % k; two equal remainders ⇔ range sum divisible by k → (normalise negative remainders: ((p % k) + k) % k) "Ranges with an even number of vowels" → prefix parity (0/1) of the vowel count — or a bitmask for several letters "Longest range with sum = target" → map prefix value → first index seen; length = i − first[R − target]
How to Spot It
✓ Many queries asking for the sum (or count) over a range ✓ "Number of subarrays with sum = k / divisible by k / balanced" ✓ Values may be NEGATIVE (rules out a sliding window) ✓ Many range ADD updates, then a single read → difference array ✓ Sums over sub-rectangles of a grid → 2D prefix
Common Mistakes
Off-by-one in the formula. With a leading 0, it's prefix[hi + 1] − prefix[lo]. Without the leading 0, it's prefix[hi] − prefix[lo − 1] and needs a special case for lo = 0. The leading 0 avoids that.
Forgetting the {0: 1} seed. Ranges starting at index 0 are silently missed.
Inserting into the map before looking up. With target 0, the current prefix would match itself and count an empty range. Look up first, then insert.
Integer overflow. Running totals of many large values exceed 32 bits — use 64-bit (long, long long).
Difference array too short. diff[hi + 1] needs size n + 1.
Interview Questions
Q: Why does counting subarrays with sum k need a map of counts, not just a set?
Several earlier positions can share the same prefix value, and each one starts a different valid range ending at the current index. A set would only record that the value appeared, undercounting those ranges; the map stores how many times each prefix value has occurred.
Q: How would you find the longest subarray with sum k (values may be negative)?
Scan with a running total and store the first index at which each prefix value appears (never overwrite it — earlier is better for "longest"). At each index i, if running − k has a stored first index j, the range j+1..i sums to k; track the maximum length. O(n) time and space.
Q: When would you choose a segment tree or Fenwick tree over a prefix array?
When values change between queries. A prefix array must be rebuilt in O(n) after each point update, while a Fenwick tree or segment tree supports both updates and range queries in O(log n).
Summary
- ›prefix[i] = sum of the first i values; any range sum is prefix[hi+1] − prefix[lo].
- ›Prefix + hash map counts or finds ranges with a target sum — works with negatives.
- ›2D prefix answers rectangle sums with inclusion–exclusion.
- ›Difference arrays turn range updates into O(1) each, with one final pass.
- ›The principle generalises to counts, parities, remainders — anything where a range is "later minus earlier".
Next, Hashing Pattern looks at the hash map itself as a problem-solving tool: complements, frequency signatures, grouping, and first-seen indices.
With prefix[0] = 0 and prefix[i+1] = prefix[i] + a[i], what is the sum of a[lo..hi] inclusive?