Prefix Sums

A prefix sum is just a running total. Walk an array once, keeping a running sum as you go, and store each partial total. Now the sum of any contiguous slice is a single subtraction away — no re-adding required.

The intuition: if you know the total up to index r and the total up to index l, then everything in between is the difference of those two totals. You trade a one-time O(n) build for O(1) answers to every range-sum query that follows.

The core identity

Define prefix[0] = 0 and prefix[i+1] = prefix[i] + arr[i]. The leading zero is the trick that makes the boundary math clean: the sum of arr[l..r] inclusive is exactly prefix[r+1] − prefix[l], with no special case for l === 0.

function buildPrefix(arr) {
  const prefix = [0]
  for (const n of arr) prefix.push(prefix.at(-1) + n)
  return prefix
}

const prefix = buildPrefix([3, 1, 4, 1, 5, 9])
// sum of arr[l..r] inclusive:
const rangeSum = (l, r) => prefix[r + 1] - prefix[l]
rangeSum(1, 3) // 1 + 4 + 1 = 6

2D prefix sums

The same idea lifts to a grid. Build a 2D prefix where P[i][j] is the sum of the rectangle from the top-left corner to (i, j). Any sub-rectangle sum is then four lookups combined by inclusion–exclusion — add the big block, subtract the two strips you double-counted, and add back the corner you subtracted twice.

Difference arrays — the inverse trick

A difference array is prefix sums run backwards. To add a value v to every element in a range [l, r], you do diff[l] += v and diff[r+1] -= v — O(1) per range update. After all updates, take the prefix sum of diff to recover the final array. This turns many range-update problems from O(n) per update into O(1).

• Range-sum queries on a static array — the canonical use.
• Subarray problems — "does a subarray sum to X?" pairs prefix sums with a hash map.
• 2D grids — image region sums, submatrix queries, and heatmaps.
• Range updates (bookings, +v over an interval) — reach for a difference array.

Subarray sum equals K

The killer application: count subarrays whose sum equals k. A subarray arr[l..r] sums to k exactly when prefix[r+1] − prefix[l] === k, i.e. prefix[l] === prefix[r+1] − k. So as you sweep the running sum, ask a hash map how many earlier prefixes equal runningSum − k. That is an O(n) solution to a problem that looks O(n²).

function subarraySumEqualsK(arr, k) {
  const seen = new Map([[0, 1]]) // empty prefix seen once
  let runningSum = 0
  let count = 0
  for (const n of arr) {
    runningSum += n
    count += seen.get(runningSum - k) ?? 0
    seen.set(runningSum, (seen.get(runningSum) ?? 0) + 1)
  }
  return count
}