Prefix Sum

The idea

If someone asks “what’s the sum of arr[l..r]?”, the naive answer is to loop from l to r — O(n) per query. With a prefix sum array, you answer it in O(1) by doing O(n) work once upfront.

Build the prefix array:

// prefix[i] = sum of arr[0] through arr[i-1]
// prefix[0] = 0  (empty prefix — makes the formula cleaner)
function buildPrefix(arr: number[]): number[] {
  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
}

Query any range in O(1):

// Sum of arr[l..r] (inclusive, 0-indexed)
function rangeSum(prefix: number[], l: number, r: number): number {
  return prefix[r + 1] - prefix[l]
}

Why the formula works:

• prefix[r+1] = sum of arr[0..r]
• prefix[l] = sum of arr[0..l-1]
• Subtracting: sum of arr[l..r]

Example: running sum queries

const arr    = [3, 1, 4, 1, 5, 9, 2, 6]
const prefix = buildPrefix(arr)
// prefix = [0, 3, 4, 8, 9, 14, 23, 25, 31]

rangeSum(prefix, 2, 5)  // arr[2..5] = 4+1+5+9 = 19
// prefix[6] - prefix[2] = 23 - 4 = 19 ✓

Classic problem 1: Subarray sum equals K

Problem: Count subarrays whose sum equals k.

Brute force is O(n²). With prefix sums and a hashmap, it’s O(n).

Key insight: sum of arr[l..r] = k means prefix[r+1] - prefix[l] = k, which means prefix[l] = prefix[r+1] - k. So as we scan, we ask: “how many previous prefix sums equal current - k?”

function subarraySum(nums: number[], k: number): number {
  const counts = new Map<number, number>()
  counts.set(0, 1)  // empty prefix has sum 0

  let prefixSum = 0, result = 0
  for (const n of nums) {
    prefixSum += n
    result += counts.get(prefixSum - k) ?? 0
    counts.set(prefixSum, (counts.get(prefixSum) ?? 0) + 1)
  }
  return result
}

This is a pattern worth memorising: prefix sum + hashmap = O(n) subarray queries.

Classic problem 2: Product array without self

Problem: Return an array output where output[i] = product of all elements except arr[i].

Constraint: no division, O(1) extra space.

The trick: build a prefix-product from the left, then multiply by a suffix-product from the right — in a single output array.

function productExceptSelf(nums: number[]): number[] {
  const n = nums.length
  const output = new Array(n).fill(1)

  // Pass 1: fill output[i] with product of all elements to the LEFT of i
  let prefix = 1
  for (let i = 0; i < n; i++) {
    output[i] = prefix
    prefix *= nums[i]
  }

  // Pass 2: multiply output[i] by product of all elements to the RIGHT of i
  let suffix = 1
  for (let i = n - 1; i >= 0; i--) {
    output[i] *= suffix
    suffix *= nums[i]
  }

  return output
}

After pass 1, output[i] = product of nums[0..i-1].
After pass 2, output[i] = product of nums[0..i-1] × nums[i+1..n-1] = product except self.

2D prefix sums (bonus)

The same idea extends to matrices for O(1) rectangle sum queries:

// prefix[r][c] = sum of the rectangle from (0,0) to (r-1, c-1)
function build2D(matrix: number[][]): number[][] {
  const rows = matrix.length, cols = matrix[0].length
  const p = Array.from({ length: rows + 1 }, () => new Array(cols + 1).fill(0))
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      p[r+1][c+1] = matrix[r][c] + p[r][c+1] + p[r+1][c] - p[r][c]
  return p
}

function query(p: number[][], r1: number, c1: number, r2: number, c2: number): number {
  return p[r2+1][c2+1] - p[r1][c2+1] - p[r2+1][c1] + p[r1][c1]
}

You won’t need this often, but it’s the natural extension of the 1D idea.

When to use

• Range sum queries (multiple queries on the same array)
• Subarray sum / count problems where a hashmap pairing is needed
• “How many subarrays satisfy condition X?” — almost always prefix + hashmap

Complexity

The O(n) space is the trade-off. For single-use range queries, just loop. Prefix sums pay off when you have multiple queries or when combined with a hashmap for more complex subarray problems.