The Prefix Sum Technique Explained

Quick Answer

The prefix sum technique precomputes running totals once, in O(n), so the sum of any range [l, r] can be answered afterward in O(1) with a single subtraction. It trades a small amount of upfront work and O(n) extra memory for turning every future range-sum query into constant time, which pays off the moment you need more than a handful of range queries against the same array.

The Problem: You Keep Summing the Same Kind of Range

Say there's an array of daily sales figures, and the question "what were total sales from day 10 to day 40?" gets asked fifty different times with fifty different ranges. The direct approach loops over the requested range and adds every element, every single time — O(r - l) per query, up to O(n) in the worst case, so O(n) per query times however many queries come in.

For 100,000 queries against an array of 100,000 elements, that's up to 10 billion additions for something that should feel instant. The fix doesn't need a tree or anything elaborate — a single array, computed once before the first query arrives, is enough.

Building the Prefix Sum Array

function buildPrefixSum(arr) {
  const prefix = new Array(arr.length + 1).fill(0);
  for (let i = 0; i < arr.length; i++) {
    prefix[i + 1] = prefix[i] + arr[i];
  }
  return prefix;
}

const arr = [4, 2, -1, 7, 3, 9, -5];
buildPrefixSum(arr);
// [0, 4, 6, 5, 12, 15, 24, 19]

prefix[i] holds the sum of the first i elements of arr — that is, arr[0] through arr[i-1]. The array is deliberately one element longer than the input, with prefix[0] = 0 standing for "the sum of zero elements." That extra leading zero isn't padding — it's what makes the range-sum formula in the next section work cleanly for ranges that start at index 0, without a special case.

Answering Any Range Sum in O(1)

function rangeSum(prefix, l, r) {
  return prefix[r + 1] - prefix[l];
}

rangeSum(prefix, 2, 4); // 9   (-1 + 7 + 3)

The intuition: prefix[r + 1] is the total of everything up to and including index r. prefix[l] is the total of everything up to but excluding index l. Subtracting the second from the first removes every element before l, leaving exactly the sum of arr[l] through arr[r] — no loop, no per-query cost, just one lookup and one subtraction regardless of how wide the range is.

This was checked against a brute-force loop over several ranges on the same array, including the full array and single-element ranges, and every result matched — the O(1) formula and the O(n) loop agree, which is exactly what should happen since they're answering the same question two different ways.

The Gotcha: prefix[r] - prefix[l] Is Off by One

The single most common bug with this technique is writing prefix[r] - prefix[l] instead of prefix[r + 1] - prefix[l] — dropping arr[r] itself out of the sum, because prefix[r] only accounts for elements up through index r - 1.

function rangeSumBuggy(prefix, l, r) {
  return prefix[r] - prefix[l];
}

rangeSumBuggy(prefix, 2, 4); // 6  -- wrong, silently drops arr[4]
rangeSum(prefix, 2, 4);      // 9  -- correct

Run against the same prefix array from above, the buggy version returns 6 — which is exactly arr[2] + arr[3], missing arr[4] entirely — while the correct version returns 9. The fix costs a single + 1, but the bug is easy to miss in review because it never throws or crashes; it just quietly returns a smaller, plausible-looking number for every range that doesn't happen to end at the last index of the array.

Extending to Two Dimensions

The same idea generalizes to a grid, answering "sum of this rectangular region" in O(1) after an O(rows × cols) build. This comes up in image processing (integral images, used for fast box blur and feature detection), spreadsheet-style range totals, and grid-based competitive programming problems.

function build2DPrefix(matrix) {
  const rows = matrix.length, cols = matrix[0].length;
  const prefix = Array.from({ length: rows + 1 }, () => new Array(cols + 1).fill(0));
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      prefix[i + 1][j + 1] = matrix[i][j] + prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j];
    }
  }
  return prefix;
}

function regionSum(prefix, r1, c1, r2, c2) {
  return prefix[r2 + 1][c2 + 1] - prefix[r1][c2 + 1] - prefix[r2 + 1][c1] + prefix[r1][c1];
}

const matrix = [
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9, 10, 11, 12],
];
const p2 = build2DPrefix(matrix);
regionSum(p2, 1, 1, 2, 2); // 34  (6 + 7 + 10 + 11)

The four-term subtraction in regionSum is inclusion-exclusion: subtracting the region above the target rectangle and the region to its left both remove the top-left corner they share, so it has to be added back once to avoid double-subtracting it. This was verified against a brute-force nested loop over several regions of the same matrix, all matching.

Where This Shows Up

Beyond direct range-sum queries, prefix sums are the backbone of a few other common patterns. "Subarray sum equals k" problems store prefix sums in a hash map while scanning once, turning an O(n²) search for matching pairs into O(n). Difference arrays flip the technique around: apply many range updates in O(1) each by marking only their endpoints, then take a single prefix sum pass at the very end to materialize every final value — useful whenever updates vastly outnumber reads, which is the opposite situation from the one a segment tree targets.

There's also a direct line back to Kadane's algorithm: the maximum subarray sum can be phrased as the maximum, over all j, of prefix[j] - min(prefix[i] for i < j) — a prefix-sum reformulation of the exact same problem Kadane's algorithm solves with a running variable instead. Recognizing when a problem is secretly a prefix-sum problem is often the entire difficulty of an otherwise easy question.

Frequently Asked Questions