The sliding window in part 2 had a condition attached: growing the window had to mean growing the quantity. One negative number and that stops being true, and the whole pattern collapses.
Prefix sums do not care. You pay once up front, and every range question after that is a subtraction.
Every program below is complete, was run on .NET 10, and its output is pasted from the run.
The trade
Console.WriteLine($"{"n",9} {"queries",9} {"scan each",16} {"prefix",12}");
foreach ((int n, int q) in new[] { (10, 5), (1_000, 1_000), (200_000, 200_000) })
{
long scan = (long)q * n; // worst case: every query spans the array
long prefix = n + q; // build once, then O(1) per query
Console.WriteLine($"{n,9:N0} {q,9:N0} {scan,16:N0} {prefix,12:N0}");
}It prints:
n queries scan each prefix
10 5 50 15
1,000 1,000 1,000,000 2,000
200,000 200,000 40,000,000,000 400,000Forty billion against four hundred thousand. That is the shape of every pattern in this part: do linear work once, then answer each question in O(1).
Pattern 11 — The prefix sum
pre[i] holds the sum of everything before index i. The array has n+1 cells, not n, and the extra one is doing real work.
The off-by-one that costs everyone an afternoon: pre is indexed by boundaries, not elements. pre[0] = 0 is the empty prefix, and it is what makes a range starting at index 0 work without a special case.
int[] a = [3, 1, 4, 1, 5, 9, 2, 6];
// pre[i] is the sum of the first i values, so pre[0] is 0 and pre.Length is n+1.
int[] pre = new int[a.Length + 1];
for (int i = 0; i < a.Length; i++) pre[i + 1] = pre[i] + a[i];
Console.WriteLine($"a = [{string.Join(", ", a)}]");
Console.WriteLine($"pre = [{string.Join(", ", pre)}]");
Console.WriteLine();
foreach ((int lo, int hi) in new[] { (0, 2), (2, 5), (5, 7), (0, 7) })
{
int sum = pre[hi + 1] - pre[lo];
Console.WriteLine($"sum a[{lo}..{hi}] = pre[{hi + 1}] - pre[{lo}] = {pre[hi + 1]} - {pre[lo]} = {sum,2} " +
$"[{string.Join(", ", a[lo..(hi + 1)])}]");
}It prints:
a = [3, 1, 4, 1, 5, 9, 2, 6]
pre = [0, 3, 4, 8, 9, 14, 23, 25, 31]
sum a[0..2] = pre[3] - pre[0] = 8 - 0 = 8 [3, 1, 4]
sum a[2..5] = pre[6] - pre[2] = 23 - 4 = 19 [4, 1, 5, 9]
sum a[5..7] = pre[8] - pre[5] = 31 - 14 = 17 [9, 2, 6]
sum a[0..7] = pre[8] - pre[0] = 31 - 0 = 31 [3, 1, 4, 1, 5, 9, 2, 6]The thing to get right is that pre is indexed by boundaries, not by elements. pre[2] is not “the value at index 2” — it is “everything before index 2”. Once you hold it that way, the range formula stops needing to be memorised:
sum a[lo..hi] = pre[hi + 1] - pre[lo]And pre[0] = 0, the empty prefix, is what lets a range starting at index 0 work with no special case. Build pre with n cells instead of n+1 and you will write that special case, get it subtly wrong, and lose twenty minutes.
Cost: O(n) to build, O(1) per query, O(n) space.
Reach for it when there are many range queries against data that does not change. If the data does change between queries, you want a Fenwick or segment tree instead — a prefix sum has to be rebuilt from the edit onwards.
Pattern 12 — Prefix sums plus a hash map
Count the subarrays summing to a target, with negative values allowed.
Here is the reframe. A subarray a[lo..hi] sums to target exactly when pre[hi+1] - pre[lo] == target, which rearranges to pre[lo] == pre[hi+1] - target. So walk the array keeping the running total, and at each step ask: have I seen the prefix running - target before, and how many times?
This is what replaces the sliding window once negative numbers are allowed. A window needs growing to mean “bigger”; a hash map of prefixes needs nothing of the sort. Seed it with {0: 1} — the empty prefix — or every subarray starting at index 0 is missed.
// Negative values, so no sliding window can solve this: growing the window
// no longer means growing the sum.
int[] a = [3, 4, 7, -2, 2, 1, 4, 2];
int target = 7;
Dictionary<int, int> seen = new() { [0] = 1 }; // one empty prefix, sum 0
int running = 0, found = 0;
for (int i = 0; i < a.Length; i++)
{
running += a[i];
int need = running - target;
int hits = seen.GetValueOrDefault(need);
if (hits > 0)
Console.WriteLine($"i={i} running={running,2} looking for {need,2} found {hits}x -> {hits} subarray(s) ending here");
else
Console.WriteLine($"i={i} running={running,2} looking for {need,2} none");
found += hits;
seen[running] = seen.GetValueOrDefault(running) + 1;
}
Console.WriteLine($"\nsubarrays summing to {target}: {found}");It prints:
i=0 running= 3 looking for -4 none
i=1 running= 7 looking for 0 found 1x -> 1 subarray(s) ending here
i=2 running=14 looking for 7 found 1x -> 1 subarray(s) ending here
i=3 running=12 looking for 5 none
i=4 running=14 looking for 7 found 1x -> 1 subarray(s) ending here
i=5 running=15 looking for 8 none
i=6 running=19 looking for 12 found 1x -> 1 subarray(s) ending here
i=7 running=21 looking for 14 found 2x -> 2 subarray(s) ending here
subarrays summing to 7: 6Two things carry this.
seen is seeded with {0: 1} before the loop starts. That entry represents the empty prefix, and without it every subarray that begins at index 0 is missed — including, here, the [3, 4] at i=1. It is the most common bug in the pattern, and it only shows up when the answer happens to start at the beginning.
The map counts occurrences rather than storing a flag, because the same prefix can occur many times and each one is a separate subarray. Look at i=7: the prefix 14 had been seen twice, so two subarrays end there.
Cost: O(n) time, O(n) space.
Reach for it when the array has negative numbers and you were reaching for a sliding window. This is the pattern that replaces it.
Pattern 13 — The difference array
Now run it backwards. You have a range of updates to apply — add 3 to everything between index 2 and 5 — and many of them, and you only need the final array at the end.
Applying each update element by element is O(range) each time. Instead, record only where each update starts and where it stops:
d[lo] += v // from here on, add v
d[hi + 1] -= v // from here on, stop adding itTwo writes, whatever the length of the range. Then one prefix-sum pass over d turns the marks back into values.
A difference array is a prefix sum run backwards. Each range update writes exactly two cells regardless of how long the range is, and a single pass at the end turns the marks into values. The 7th cell exists so that hi+1 is always in range; it is discarded.
int n = 6;
int[] diff = new int[n + 1]; // one extra cell, so hi+1 is always in range
(int lo, int hi, int v)[] updates = [(1, 3, +2), (2, 5, +3), (0, 2, -1)];
foreach ((int lo, int hi, int v) in updates)
{
diff[lo] += v;
diff[hi + 1] -= v;
Console.WriteLine($"add {v,2} to [{lo}..{hi}] diff[{lo}] {v:+#;-#;0}, diff[{hi + 1}] {-v:+#;-#;0} " +
$"-> [{string.Join(", ", diff)}]");
}
int[] final = new int[n];
int running = 0;
for (int i = 0; i < n; i++) { running += diff[i]; final[i] = running; }
Console.WriteLine($"\nrunning sum of diff -> [{string.Join(", ", final)}]");
// Brute force, to prove it.
int[] check = new int[n];
foreach ((int lo, int hi, int v) in updates)
for (int i = lo; i <= hi; i++) check[i] += v;
Console.WriteLine($"element by element -> [{string.Join(", ", check)}]");
Console.WriteLine($"same: {final.SequenceEqual(check)}");It prints:
add 2 to [1..3] diff[1] +2, diff[4] -2 -> [0, 2, 0, 0, -2, 0, 0]
add 3 to [2..5] diff[2] +3, diff[6] -3 -> [0, 2, 3, 0, -2, 0, -3]
add -1 to [0..2] diff[0] -1, diff[3] +1 -> [-1, 2, 3, 1, -2, 0, -3]
running sum of diff -> [-1, 1, 4, 5, 3, 3]
element by element -> [-1, 1, 4, 5, 3, 3]
same: TrueThe brute-force check at the end is there because this one looks like it should not work.
d is allocated with n + 1 cells so that d[hi + 1] is in range when hi is the last index. That last cell is never read by the reconstruction — it exists purely so the “stop adding” write always has somewhere to go.
Cost: O(1) per update, O(n) once at the end.
Reach for it when the problem is m range updates followed by reading the result — booking systems, flight seat counts, “how many intervals cover each point”. If updates and queries are interleaved, you need a Fenwick tree instead.
Pattern 14 — Two dimensions
Same idea, one more axis. pre[r][c] holds the sum of everything strictly above row r and strictly left of column c.
Building it needs inclusion–exclusion, and so does querying it. The corner region belongs to both the strip above and the strip to the left, so subtracting both removes it twice.
The corner region sits inside both the strip above and the strip to the left, so subtracting both removes it twice. Adding it back once is not a correction bolted on afterwards — it is what inclusion–exclusion is.
int[,] g = {
{ 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 },
};
int rows = g.GetLength(0), cols = g.GetLength(1);
// pre[r, c] = sum of everything strictly above row r and left of column c.
int[,] pre = new int[rows + 1, cols + 1];
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++)
pre[r + 1, c + 1] = g[r, c] + pre[r, c + 1] + pre[r + 1, c] - pre[r, c];
Console.WriteLine("pre:");
for (int r = 0; r <= rows; r++)
{
for (int c = 0; c <= cols; c++) Console.Write($"{pre[r, c],5}");
Console.WriteLine();
}
int Query(int r1, int c1, int r2, int c2) =>
pre[r2 + 1, c2 + 1] - pre[r1, c2 + 1] - pre[r2 + 1, c1] + pre[r1, c1];
Console.WriteLine();
foreach ((int r1, int c1, int r2, int c2) in new[] { (1, 1, 2, 2), (0, 0, 1, 1), (2, 0, 3, 3) })
{
int brute = 0;
for (int r = r1; r <= r2; r++) for (int c = c1; c <= c2; c++) brute += g[r, c];
Console.WriteLine($"rows {r1}..{r2}, cols {c1}..{c2} -> {Query(r1, c1, r2, c2),3} (brute force {brute,3})");
}It prints:
pre:
0 0 0 0 0
0 1 3 6 10
0 6 14 24 36
0 15 33 54 78
0 28 60 96 136
rows 1..2, cols 1..2 -> 34 (brute force 34)
rows 0..1, cols 0..1 -> 14 (brute force 14)
rows 2..3, cols 0..3 -> 100 (brute force 100)Both the build and the query use the same + - - + shape, and they use it for the same reason. If you can only remember one thing, remember that the last term is a plus and it is the corner you took away twice.
Cost: O(rows × cols) to build, O(1) per query.
Reach for it when the queries are rectangles in a grid. Image problems, matrix sums, and any “count things inside this box” question.
Pattern 15 — Prefix XOR
XOR behaves enough like addition for all of this to carry over, because it is its own inverse: x ^ y ^ y == x. So the prefix trick works with ^ in place of +, and subtraction becomes another ^.
The rearrangement is the only step worth slowing down for:
running ^ need == target // what we want
need == running ^ target // xor both sides by runningint[] a = [4, 2, 2, 6, 4];
int target = 6;
Dictionary<int, int> seen = new() { [0] = 1 };
int running = 0, found = 0;
for (int i = 0; i < a.Length; i++)
{
running ^= a[i];
int need = running ^ target; // because x ^ need == target => need == x ^ target
int hits = seen.GetValueOrDefault(need);
found += hits;
Console.WriteLine($"i={i} a[i]={a[i]} prefixXor={running} need={need} matches={hits}");
seen[running] = seen.GetValueOrDefault(running) + 1;
}
Console.WriteLine($"\nsubarrays with XOR {target}: {found}");
int brute = 0;
for (int i = 0; i < a.Length; i++)
{
int x = 0;
for (int j = i; j < a.Length; j++) { x ^= a[j]; if (x == target) brute++; }
}
Console.WriteLine($"brute force: {brute}");It prints:
i=0 a[i]=4 prefixXor=4 need=2 matches=0
i=1 a[i]=2 prefixXor=6 need=0 matches=1
i=2 a[i]=2 prefixXor=4 need=2 matches=0
i=3 a[i]=6 prefixXor=2 need=4 matches=2
i=4 a[i]=4 prefixXor=6 need=0 matches=1
subarrays with XOR 6: 4
brute force: 4Structurally identical to pattern 12 — same seeded map, same counting — with + swapped for ^. That is the point of including it: once you see prefix sums as “any operation with an inverse”, the family gets much larger than addition.
Cost: O(n) time, O(n) space.
Reach for it when the problem is about XOR of ranges. It also generalises to products, if you are careful about zeros, and to any associative operation with an inverse.
What to remember
-
preis indexed by boundaries, not elements.n+1cells,pre[0] = 0, andsum a[lo..hi] = pre[hi+1] - pre[lo]with no special case at the start. -
Prefix sums are what you use when a sliding window will not work. The moment negatives appear, growing the window stops meaning growing the sum, and the window has nothing to hold on to.
-
Seed the map with
{0: 1}. It is the empty prefix. Leave it out and every answer starting at index 0 disappears — including on inputs where nothing else looks wrong. -
Count occurrences in the map, not presence. The same prefix recurring is the same target hit again.
-
A difference array turns a range update into two writes.
d[lo] += v,d[hi+1] -= v, then one pass. Allocaten+1cells so the second write always lands. -
In 2D, the last term of the query is a plus. The corner was subtracted twice, by the strip above and the strip to the left.
-
It is not really about addition. Any operation with an inverse works, which is why the XOR version is the same code with one character changed.
Part 4 is binary search, and specifically the two thirds of it that are not “find this element in a sorted array”.