Prefix Sums & Difference Arrays

The 10-second versionCopy Anchor Link

A prefix sum is a running total you build once: P[i] holds the sum of the first i elements. With it, the sum of any range [l, r) is one subtraction — P[r] - P[l] — no matter how wide that range is, and no matter how many times you ask. Flip the same array backwards and you get the difference array: it turns "add v to every element in a range" into two point-updates. Build once, then every query is instant.

Why this existedCopy Anchor Link

The problem is embarrassingly old and embarrassingly common: answer many range queries fast. A dashboard asks "how many sign-ups between March and June?" a million times. A database counts rows in a range. A graphics routine sums the pixels in a rectangle. Re-adding the range every single time is O(n) per query, and n queries make it O(n²) — death by a thousand sums.

The fix — keep cumulative totals and difference them — is such a natural idea that it shows up in wildly different fields, each time as a breakthrough:

• 1984 — Frank Crow introduces summed-area tables in Summed-Area Tables for Texture Mapping. This is the 2D prefix sum: one array that answers the sum of any rectangle in constant time, used to make textures blur correctly.
• Late 1980s — Guy Blelloch and others develop the parallel prefix sum (the "scan" primitive). Computing all prefix sums in parallel with a work-efficient tree makes it a fundamental data-parallel building block, not just a lookup trick.
• 2001 — Viola and Jones build real-time face detection on the integral image — Crow's 2D prefix sum again, now cheap enough to scan a video frame dozens of times per second.

Why it mattered: it's the cheapest form of precomputation there is. You don't add a tree or a hash map — you add one array, and a whole class of queries drops from O(n) to O(1). That asymmetry, built once and read forever, is the entire idea.

Inside the inventor's headCopy Anchor Link

Look at the problem pattern: you have an array, and you're going to be asked for the sum of [l, r) over and over, with different l and r each time. The honest answer is to loop:

// answer each query by re-adding the range — O(n) per queryfunction rangeSumNaive(a, l, r) {  let sum = 0;  for (let i = l; i < r; i++) sum += a[i];  return sum;}

If you have q queries, that's O(n · q) — and if q grows with n, you're quadratic again.

Watch the first failed instinct: "precompute every possible range sum." There are n(n+1)/2 of them, so that's an O(n²) table — you've traded time for even more time and memory. Too greedy.

That's the pivot. The O(n²) table is wasteful because it stores redundant information — every range sum is just the difference between two running totals. Store only the n + 1 totals (starting with an empty P[0] = 0), and the subtraction recovers any range exactly. The empty leading slot is the trick that makes the formula uniform: it's the reason [0, r) needs no special case.

The final approachCopy Anchor Link

The algorithmCopy Anchor Link

Build the prefix array left to right, then answer each query with one subtraction.

The invariantsCopy Anchor Link

• Coverage. P[i] always equals a[0] + a[1] + … + a[i-1]; P[0] = 0 is the empty sum.
• Range identity. For any l ≤ r, the sum of a[l … r-1] equals P[r] - P[l]. Everything before l is in both totals and cancels.
• Difference duality. A difference array D and a prefix sum are inverses: prefix-summing D yields the array whose range updates D encodes.

A worked traceCopy Anchor Link

Take a = [2, 4, 1, 7, 3]. Build the prefix array:

Now the sum of [1, 4) (that's a[1] + a[2] + a[3] = 4 + 1 + 7 = 12) is just P[4] - P[1] = 14 - 2 = 12. One subtraction — no matter that the range is three wide.

Difference arrays: the same idea backwardsCopy Anchor Link

Prefix sums answer range queries. Difference arrays handle range updates: "add v to every element in [l, r)," repeated many times. Naively that's O(n) per update. Instead, record the change as two events — +v where the bump starts, -v where it stops — and prefix-sum the events once at the end.

It in codeCopy Anchor Link

function buildPrefix(a) {  const P = [0];  for (let i = 0; i < a.length; i++) P.push(P[i] + a[i]);  return P;}// sum of a[l .. r-1] in O(1)const rangeSum = (P, l, r) => P[r] - P[l];

// start from all zeros; add v to every index in [l, r)function rangeAdd(D, l, r, v) { D[l] += v; D[r] -= v; }function finalize(D, n) {  const out = [];  let run = 0;  for (let i = 0; i < n; i++) { run += D[i]; out.push(run); }  return out;}

CostCopy Anchor Link

Across a run of q queries the prefix array turns O(n·q) into O(n + q) — the build is paid once and every query is free.

Where you meet it todayCopy Anchor Link

• Time-series analytics. "How many events between t1 and t2?" over a histogram is a prefix-sum lookup; dashboards and databases do this constantly.
• Image processing. The integral image is a 2D prefix sum: it sums any rectangular patch in O(1), which is exactly how the Viola-Jones face detector and fast box blurs work.
• Databases. Running totals and some SUM(...) OVER window functions are prefix sums the optimizer already knows how to exploit.
• Contest arithmetic. Subarray-sum-counting, "number of subarrays with sum k," and offline range queries all start by building a prefix array.

// sum[i][j] = sum of the rectangle from (0,0) to (i-1, j-1)function buildIntegral(img, w, h) {  const sum = Array.from({ length: h + 1 }, () => new Array(w + 1).fill(0));  for (let i = 1; i <= h; i++)    for (let j = 1; j <= w; j++)      sum[i][j] = img[i - 1][j - 1]                + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];  return sum;}// sum of the rectangle [r1, r2) x [c1, c2) in O(1)const boxSum = (sum, r1, c1, r2, c2) =>  sum[r2][c2] - sum[r1][c2] - sum[r2][c1] + sum[r1][c1];

That rectangle formula is inclusion–exclusion: add the two overlapping prefixes, subtract the double-counted corner, subtract the part hanging above-left. Four array reads for any rectangle.

RecapCopy Anchor Link

• A prefix sum is a running total: P[i] = P[i-1] + a[i-1], with P[0] = 0 the empty sum.
• Any range sum is P[r] - P[l] — build once in O(n), then answer in O(1) forever.
• A difference array is the inverse: range adds become +v / -v events, materialized by prefix-summing once.
• The 2D version is the integral image — O(1) rectangle sums via inclusion–exclusion.

Next up: Kadane's Algorithm & Running State — carrying one number forward instead of a whole array of totals.