jsschools

Prefix Sum (Cumulative Sum)

Precomputes cumulative sums so that the sum of any subarray arr[l..r] can be answered in O(1) after an O(n) build phase.

Spec ↗

Syntax

buildPrefix(arr)

Parameters

NameTypeRequiredDescription
arr number[] Yes Input array of numbers.

Returns

number[] — Prefix sum array where prefix[i] = arr[0] + arr[1] + ... + arr[i-1]. Length is arr.length + 1 (with a leading 0).

Examples

function buildPrefix(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;
}

function rangeSum(prefix, l, r) {
  return prefix[r + 1] - prefix[l]; // sum of arr[l..r] inclusive
}

const arr = [1, 3, 5, 7, 9, 11];
const prefix = buildPrefix(arr);
console.log(rangeSum(prefix, 1, 3)); // 3+5+7 = 15
console.log(rangeSum(prefix, 0, 5)); // entire array
Output 
15
36

// 2D prefix sum for rectangle queries
function build2D(matrix) {
  const m = matrix.length, n = matrix[0].length;
  const pre = Array.from({length: m+1}, () => new Array(n+1).fill(0));
  for (let i = 1; i <= m; i++)
    for (let j = 1; j <= n; j++)
      pre[i][j] = matrix[i-1][j-1] + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1];
  return pre;
}

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

const mat = [[1,2,3],[4,5,6],[7,8,9]];
const pre = build2D(mat);
console.log(rectSum(pre, 0, 0, 1, 1)); // top-left 2×2 = 1+2+4+5 = 12
Output 
12

Notes

| Operation | Time | Space | |-------------|------|-------| | Build | O(n) | O(n) | | Range query | O(1) | O(1) | With the leading-zero sentinel `prefix[0] = 0`, the range sum formula `prefix[r+1] - prefix[l]` is clean and free of off-by-one errors. Prefix sums can be extended to 2D (inclusion-exclusion), difference arrays (range increment in O(1)), and applied to problems like counting subarrays with a given sum using a hash map over prefix values. Kadane's algorithm can be seen as a specialised prefix-sum problem.

See also