Things

Prefix Sum

12 min read

Used in: Find the Highest Altitude (LC 1732), Find Pivot Index (LC 724)
Related: Two Pointers, Kids With the Greatest Number of Candies (LC 1431), Sliding Window, Fenwick Tree
Time: O(n) to build, O(1) per range query | Space: O(n), or O(1) if you only need a running total

What is it?

A prefix sum array stores, at each position, the total of everything before it. Once you have it, the sum of any contiguous range is one subtraction.

a      =    [3, 1, 4, 1,  5,  9,  2]
prefix = [0, 3, 4, 8, 9, 14, 23, 25]

prefix[i] is the sum of the first i elements. Sum of a[2..4] (that’s 4 + 1 + 5) = prefix[5] - prefix[2] = 14 - 4 = 10.

Running totals turn “add up this range” into “subtract two totals”.

It’s the same idea as a bank statement’s running balance. To find out how much you spent between the 3rd and the 10th, you don’t re-add every transaction. You subtract the balance on the 3rd from the balance on the 10th.

Why it exists

Answering one range sum by looping is O(length of range). Fine once. But if you get many queries on the same array, it’s O(n) each, so q queries cost O(n · q).

Prefix sums pay O(n) once and then every query is O(1). I timed it in Node: 100,000 queries over a 100,000-element array took 9,179 ms with a loop per query and 5 ms with a prefix array. Same answers.

The trade only works because addition can be undone. You can subtract a prefix back out. That’s the key property, and it’s why the trick works for sums, counts and XOR, but not directly for max or min (you can’t “un-max” something).

Building it

The n + 1 version (use this)

function buildPrefix(a: number[]): number[] {
  const prefix = new Array(a.length + 1).fill(0);
  for (let i = 0; i < a.length; i++) {
    prefix[i + 1] = prefix[i] + a[i];
  }
  return prefix;
}
 
// sum of a[l..r], both ends included
const rangeSum = (prefix: number[], l: number, r: number) => prefix[r + 1] - prefix[l];

The leading 0 means “the sum of nothing”. It’s what makes the formula work when l = 0 without an if. Without it you’d write l === 0 ? prefix[r] : prefix[r] - prefix[l - 1], and that’s where off-by-one bugs come from.

Read it as: prefix[i] = sum of a[0 .. i-1]. Half-open, like slice(0, i).

The running-total version (no array)

Often you don’t need random access, just the total “so far” as you scan. Then a single variable is enough.

let sum = 0;
for (const x of a) {
  sum += x;   // sum is now the prefix sum ending here
}

Most LeetCode problems tagged “prefix sum” are really this.

The shapes

1. Range sum queries

Build once, answer many. LC 303 Range Sum Query is exactly this. The code is above.

2. Running total with a best-so-far

Track the running total and the best value it ever reached.

// LC 1732 Find the Highest Altitude: gain[i] is the change between points
function largestAltitude(gain: number[]): number {
  let altitude = 0, best = 0;   // you start at altitude 0, and that counts
  for (const g of gain) {
    altitude += g;
    best = Math.max(best, altitude);
  }
  return best;
}
// [-5,1,5,0,-7] → 1      [-4,-3,-2,-1,4,3,2] → 0

3. Left total vs right total

Total minus left minus the current element is the right side. No second array needed.

// LC 724 Find Pivot Index
function pivotIndex(nums: number[]): number {
  const total = nums.reduce((s, x) => s + x, 0);
  let left = 0;
  for (let i = 0; i < nums.length; i++) {
    const right = total - left - nums[i];
    if (left === right) return i;
    left += nums[i];       // update AFTER the check: nums[i] isn't on its own left
  }
  return -1;
}
// [1,7,3,6,5,6] → 3     [1,2,3] → -1     [2,1,-1] → 0 (left of index 0 is empty, so 0)

4. Prefix sum + hash map (the big one)

“Count subarrays whose sum is k.” The sum of a[j..i] is prefix[i+1] - prefix[j]. You want that to equal k, so you’re looking for an earlier prefix equal to currentPrefix - k. Keep a map of how many times you’ve seen each prefix.

// LC 560 Subarray Sum Equals K
function subarraySum(nums: number[], k: number): number {
  const seen = new Map<number, number>([[0, 1]]);  // the empty prefix
  let sum = 0, count = 0;
  for (const x of nums) {
    sum += x;
    count += seen.get(sum - k) ?? 0;
    seen.set(sum, (seen.get(sum) ?? 0) + 1);
  }
  return count;
}
// [1,1,1], k=2 → 2      [1,2,3], k=3 → 2      [1,-1,0], k=0 → 3

The [0, 1] seed is the empty prefix. It counts subarrays that start at index 0. Leave it out and [1,2,3], k=3 returns 1 instead of 2, because [1,2] gets missed. Same reason as the leading 0 in the array version.

This works with negative numbers, which is exactly where Sliding Window fails. A sliding window assumes growing the window grows the sum. With negatives that’s false, so you can’t decide when to shrink. Prefix sum + map doesn’t care.

Variations of the same pattern:

ProblemWhat you store in the mapTrick
Count subarrays with sum k (LC 560)prefix → countlook up sum - k
Subarray sums divisible by k (LC 974)sum mod k → countequal remainders means the difference divides by k
Longest subarray with equal 0s and 1s (LC 525)prefix → first indextreat 0 as -1, look for a repeated prefix. Seed with 0 → -1
Continuous subarray sum (LC 523)sum mod k → first indexsame, plus “length at least 2”

For longest, store the first index you saw each prefix and never overwrite it. For count, store how many times you’ve seen it.

// LC 525 Contiguous Array
function findMaxLength(nums: number[]): number {
  const first = new Map<number, number>([[0, -1]]);
  let sum = 0, best = 0;
  nums.forEach((x, i) => {
    sum += x === 1 ? 1 : -1;
    if (first.has(sum)) best = Math.max(best, i - first.get(sum)!);
    else first.set(sum, i);
  });
  return best;
}
// [0,1] → 2    [0,0,1,0,0,0,1,1] → 6

5. Prefix products (and why division is avoided)

LC 238 Product of Array Except Self: product of everything to the left times product of everything to the right. Same idea, but with *, and you can’t subtract (or safely divide, because of zeros), so you do two passes.

function productExceptSelf(nums: number[]): number[] {
  const n = nums.length, out = new Array(n).fill(1);
  let left = 1;
  for (let i = 0; i < n; i++) { out[i] = left; left *= nums[i]; }
  let right = 1;
  for (let i = n - 1; i >= 0; i--) { out[i] *= right; right *= nums[i]; }
  return out;
}
// [1,2,3,4] → [24,12,8,6]

In JS, [-1,1,0,-3,3] returns [-0, 0, 9, -0, 0]. -0 === 0 is true, so tests pass, but Object.is and some snapshot tools tell them apart.

6. Prefix XOR

XOR is its own inverse (x ^ x = 0), so xor(a[l..r]) = px[r+1] ^ px[l]. Same code with ^ instead of + and -. LC 1310 XOR Queries of a Subarray.

7. 2D prefix sums (summed-area table)

P[r][c] = sum of the rectangle from (0,0) to (r-1, c-1). Build and query with inclusion-exclusion:

const R = grid.length, C = grid[0].length;
const P = Array.from({ length: R + 1 }, () => new Array(C + 1).fill(0));
for (let r = 0; r < R; r++)
  for (let c = 0; c < C; c++)
    P[r + 1][c + 1] = grid[r][c] + P[r][c + 1] + P[r + 1][c] - P[r][c];
 
// sum of rectangle rows r1..r2, cols c1..c2 (inclusive)
const rect = (r1: number, c1: number, r2: number, c2: number) =>
  P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1];

Picture it: the big rectangle, minus the strip above, minus the strip to the left, plus the top-left corner back because you subtracted it twice. LC 304 Range Sum Query 2D.

8. Difference arrays (prefix sum in reverse)

The inverse problem: many range updates, then read the final array once. “Add 10 to positions 0 to 2, add 5 to 1 to 4, subtract 2 at 3.”

Mark only the edges, then prefix-sum at the end:

const n = 5, diff = new Array(n + 1).fill(0);
for (const [l, r, v] of [[0, 2, 10], [1, 4, 5], [3, 3, -2]]) {
  diff[l] += v;       // starts here
  diff[r + 1] -= v;   // stops after r
}
const out = [];
let run = 0;
for (let i = 0; i < n; i++) { run += diff[i]; out.push(run); }
// [10, 15, 15, 3, 5]

Each update is O(1) instead of O(range). LC 1094 Car Pooling and LC 1109 Corporate Flight Bookings are this exactly. Bonus: a “sweep line” over events (+1 when a meeting starts, -1 when it ends) is a difference array over time.

When it stops working

  • The array changes between queries. One update at index i changes every prefix[j] for j > i, so it’s O(n). Use a Fenwick Tree (binary indexed tree) or a segment tree: O(log n) for both update and query.
  • Max, min or gcd over a range. No inverse, so no subtraction. Use a sparse table (static data) or a segment tree.
  • Only one query. Just loop. Building the array is the same work.
NeedToolBuildQueryUpdate
Static array, many sum queriesPrefix sumO(n)O(1)O(n)
Many range updates, one readDifference arrayO(n)O(n) onceO(1)
Updates and queries mixedFenwick / segment treeO(n)O(log n)O(log n)
Static, range min/maxSparse tableO(n log n)O(1)rebuild

Cues: when to reach for it

  • “Sum of a subarray / range” asked many times.
  • “Count subarrays with sum / XOR equal to k”. ⭐ Strongest cue, especially with negative numbers allowed.
  • “Left side equals right side”, “balance point”, “pivot”.
  • “Equal number of X and Y” → map one to +1, the other to -1, look for repeated prefixes.
  • “Divisible by k” → prefix sums mod k.
  • “Apply many range increments” → difference array.
  • Rectangle sums in a grid → 2D prefix.

A real-world example

A text editor needs to turn a character offset (from a cursor, a search hit or a collaborator’s edit) into a line number:

  • Keep a prefix array of line start offsets: for "ab\ncde\n\nf" that’s [0, 3, 7, 8]. It’s a prefix sum of line lengths (each including its newline).
  • Offset → line is a binary search for the last start <= offset. Offset 4 → line 1, offset 7 → line 2. O(log n) instead of counting newlines from the top every time.
  • Line → offset is a direct lookup.
  • Because edits change the array, editors that handle huge files keep these sums in a balanced tree (the Fenwick Tree idea), so an edit on line 10 doesn’t rewrite the offsets of the next million lines.

Same idea elsewhere:

  • SQL SUM(amount) OVER (ORDER BY day) is a running total computed by the database. A dashboard’s “last 7 days” from a daily-totals table is cumulative[today] - cumulative[today - 7].
  • Image processing uses 2D summed-area tables to get the average of any rectangle in O(1). That’s how a box blur stays fast at any radius.
  • GPUs run a parallel version called a scan as a building block for sorting and stream compaction.

Gotchas

  • Off by one. Use the n + 1 array with a leading 0 and the formula prefix[r + 1] - prefix[l]. Don’t mix conventions in one solution.
  • Forgetting the empty prefix in the hash map version ([0, 1] for counting, 0 → -1 for longest). It silently misses subarrays starting at index 0.
  • Map update order. Look up sum - k before inserting the current sum. Otherwise with k = 0 every element matches itself.
  • Negative modulo in JS. -7 % 5 is -2, not 3. Normalise with ((sum % k) + k) % k. On [-1, 2, 9] with k = 2, the plain % version returned 1 instead of 2.
  • Overflow. Sums grow. JS numbers are exact only up to 2^53 - 1 (Number.MAX_SAFE_INTEGER). In Java and C++, prefix sums of int arrays often need long.
  • Floats drift. Prefix sums of [0.1, 0.2, 0.3] give prefix[3] - prefix[1] = 0.5000000000000001. For money, store integer cents.
  • Pivot index: update left after the comparison, not before.
  • Sliding window vs prefix + map. All non-negative numbers → sliding window works and uses O(1) space. Negatives allowed → prefix + map.

Practice

  1. Find the Highest Altitude (LC 1732) → running total with best-so-far
  2. Find Pivot Index (LC 724) → left vs right
  3. Range Sum Query - Immutable (LC 303) → the basic array
  4. Product of Array Except Self (LC 238) → prefix products, two passes
  5. Subarray Sum Equals K (LC 560) → prefix + map, count
  6. Contiguous Array (LC 525) → prefix + map, longest, ±1 trick
  7. Subarray Sums Divisible by K (LC 974) → mod k, watch negatives
  8. Range Sum Query 2D - Immutable (LC 304) → summed-area table
  9. Corporate Flight Bookings (LC 1109) → difference array
  10. Range Sum Query - Mutable (LC 307) → where prefix sums stop working, do it with a Fenwick tree

Sources worth reading

  • CP-Algorithms, “Fenwick Tree” and “Sparse Table”, for what to use when prefix sums aren’t enough: https://cp-algorithms.com/
  • USACO Guide, “Prefix Sums” and “More on Prefix Sums” (2D and difference arrays): https://usaco.guide/silver/prefix-sums
  • Wikipedia, “Summed-area table” and “Prefix sum” (includes the parallel scan algorithms)
  • GPU Gems 3, chapter 39, “Parallel Prefix Sum (Scan) with CUDA”

Graph View

Backlinks