Prefix Sums

A prefix-sum array lets you answer "what is the sum of elements from index i to j?" in O(1) after a single O(n) preprocessing pass, and extends to finding subarray sums equal to a target via a hashmap.

5 min read Level 2/5 #dsa#arrays#prefix-sums

What you'll learn

Build a 1D prefix-sum array and derive range sums in O(1)
Solve the subarray-sum-equals-k problem using a prefix-sum hashmap
Describe how 2D prefix sums extend the technique to matrices

A prefix sum (also called a cumulative sum) at index i stores the total of all elements from index 0 up to i. With this auxiliary array precomputed, the sum of any subarray nums[i..j] is a single subtraction.

Building a 1D Prefix Sum

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

// Range sum query: sum of nums[i..j] inclusive
function rangeSum(prefix, i, j) {
  return prefix[j + 1] - prefix[i];
}

const nums = [3, 1, 4, 1, 5, 9, 2, 6];
const prefix = buildPrefix(nums);

console.log(rangeSum(prefix, 1, 4)); // 1+4+1+5 = 11
console.log(rangeSum(prefix, 0, 7)); // sum of all = 31

The prefix array has length n + 1, with prefix[0] = 0 acting as a sentinel so that rangeSum(prefix, 0, j) works without a special case.

Subarray Sum Equals K

A clever extension uses a hashmap to track how many times each prefix sum has occurred. If prefix[j] - prefix[i] === k, then the subarray nums[i..j-1] sums to k. Rearranging: at each j, we look for prefix[j] - k in the map.

function subarraySum(nums, k) {
  const counts = new Map([[0, 1]]); // prefix sum 0 seen once (before any element)
  let sum = 0;
  let result = 0;

  for (const num of nums) {
    sum += num;
    const complement = sum - k;
    if (counts.has(complement)) {
      result += counts.get(complement);
    }
    counts.set(sum, (counts.get(sum) ?? 0) + 1);
  }
  return result;
}

// Walk-through: nums = [1, 2, 3], k = 3
// num=1: sum=1, look for -2 → no. map: {0:1, 1:1}
// num=2: sum=3, look for  0 → found 1 time → result=1. map: {0:1,1:1,3:1}
// num=3: sum=6, look for  3 → found 1 time → result=2. map: {0:1,1:1,3:1,6:1}
console.log(subarraySum([1, 2, 3], 3)); // 2 ([1,2] and [3])

2D Prefix Sums (Overview)

The technique extends to grids. P[r][c] = sum of all cells in the rectangle from (0,0) to (r,c). A rectangle query (r1,c1)→(r2,c2) then uses inclusion-exclusion:

sum = P[r2][c2] - P[r1-1][c2] - P[r2][c1-1] + P[r1-1][c1-1]

This is commonly needed in 2D DP problems and image processing (summed-area table).

Complexity

Operation	Time	Space
Build 1D prefix	O(n)	O(n)
Single range query	O(1)	O(1)
Subarray sum = k (hashmap)	O(n)	O(n)
Build 2D prefix	O(r * c)	O(r * c)
2D rectangle query	O(1)	O(1)

Up Next

Kadane’s algorithm finds the maximum-sum subarray in O(n) — a problem where prefix sums alone would require an O(n²) scan over all pairs.

Kadane's Algorithm →