Prefix Sum

The prefix sum (also called the cumulative sum) is one of the most versatile preprocessing tricks in competitive programming. Spend O(n) time once to build the prefix array, then answer any range-sum query in O(1).

Building the Prefix Array

Given an array nums, define prefix[i] as the sum of all elements from index 0 up to and including index i−1 (using a 1-indexed sentinel at position 0 makes the formulas cleaner):

prefix[0] = 0 prefix[i] = prefix[i-1] + nums[i-1]

Then the sum of any subarray nums[l..r] (inclusive, 0-indexed) is just:

sum(l, r) = prefix[r+1] - prefix[l]

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 O(1)
function rangeSum(prefix, l, r) {
  return prefix[r + 1] - prefix[l]; // sum of nums[l..r] inclusive
}

const nums   = [1, 3, 5, 7, 9];
const prefix = buildPrefix(nums); // [0, 1, 4, 9, 16, 25]

console.log(rangeSum(prefix, 1, 3)); // 3+5+7 = 15
console.log(rangeSum(prefix, 0, 4)); // 1+3+5+7+9 = 25
console.log(rangeSum(prefix, 2, 2)); // 5

Note

Build: O(n) time, O(n) space. Query: O(1). The 1-indexed prefix array (size n+1 with prefix[0] = 0) avoids the edge-case special-casing you need with 0-indexed arrays.

Range Sum Query (Immutable) — LeetCode 303

class NumArray {
  constructor(nums) {
    this.prefix = new Array(nums.length + 1).fill(0);
    for (let i = 0; i < nums.length; i++) {
      this.prefix[i + 1] = this.prefix[i] + nums[i];
    }
  }

  // Returns sum of nums[left..right] inclusive
  sumRange(left, right) {
    return this.prefix[right + 1] - this.prefix[left];
  }
}

const obj = new NumArray([-2, 0, 3, -5, 2, -1]);
console.log(obj.sumRange(0, 2)); //  1  (-2+0+3)
console.log(obj.sumRange(2, 5)); // -1  (3-5+2-1)
console.log(obj.sumRange(0, 5)); // -3

Subarray Sum Equals K — LeetCode 560

Count the number of contiguous subarrays whose sum equals k.

The naive approach checks all O(n²) pairs (l, r). With prefix sums and a hash map you can do it in O(n):

For each index r, you want the number of l values where prefix[r] - prefix[l] = k, i.e. prefix[l] = prefix[r] - k. Keep a running count map of how many times each prefix value has been seen so far.

function subarraySum(nums, k) {
  const prefixCount = new Map([[0, 1]]); // prefix sum → # of times seen
  let runningSum = 0, count = 0;

  for (const n of nums) {
    runningSum += n;
    // How many previous prefixes make a valid subarray ending here?
    count += prefixCount.get(runningSum - k) ?? 0;
    prefixCount.set(runningSum, (prefixCount.get(runningSum) ?? 0) + 1);
  }
  return count;
}

console.log(subarraySum([1,1,1], 2)); // 2
console.log(subarraySum([1,2,3], 3)); // 2  ([1,2] and [3])

Tip

Initialise the map with {0: 1} to handle the case where the subarray starts at index 0 (the entire prefix equals k).

Find Pivot Index — LeetCode 724

The pivot index is the position where the sum of all elements to the left equals the sum of all elements to the right. Compute the total sum once, then scan left-to-right maintaining a left running sum. At each index: leftSum === totalSum - leftSum - nums[i].

function pivotIndex(nums) {
  const total = nums.reduce((a, b) => a + b, 0);
  let leftSum = 0;

  for (let i = 0; i < nums.length; i++) {
    // right sum = total - leftSum - nums[i]
    if (leftSum === total - leftSum - nums[i]) return i;
    leftSum += nums[i];
  }
  return -1;
}

console.log(pivotIndex([1,7,3,6,5,6])); // 3
console.log(pivotIndex([1,2,3]));        // -1
console.log(pivotIndex([2,1,-1]));       // 0

Product of Array Except Self — LeetCode 238

Return an array where output[i] is the product of every element except nums[i]. No division allowed; do it in O(n) time and O(1) extra space.

Two passes:

Left pass: left[i] = product of all elements to the left of i.
Right pass: multiply by the running product of everything to the right.

function productExceptSelf(nums) {
  const n = nums.length;
  const result = new Array(n).fill(1);

  // Left pass: result[i] = product of nums[0..i-1]
  let leftProduct = 1;
  for (let i = 0; i < n; i++) {
    result[i] = leftProduct;
    leftProduct *= nums[i];
  }

  // Right pass: multiply result[i] by product of nums[i+1..n-1]
  let rightProduct = 1;
  for (let i = n - 1; i >= 0; i--) {
    result[i] *= rightProduct;
    rightProduct *= nums[i];
  }
  return result;
}

console.log(productExceptSelf([1,2,3,4]));  // [24,12,8,6]
console.log(productExceptSelf([-1,1,0,-3,3])); // [0,0,9,0,0]

Difference Array — Range Updates in O(1)

The difference array is the inverse of the prefix sum: instead of answering range queries after a fixed array, it lets you apply range updates in O(1) and read the final array in O(n).

Given an update "add v to all elements in [l, r]", mark:

diff[l] += v
diff[r+1] -= v

After all updates, compute the prefix sum of diff to get the final array.

class DifferenceArray {
  constructor(n) {
    this.diff = new Array(n + 1).fill(0);
  }

  // Add val to every element in range [l, r] — O(1)
  update(l, r, val) {
    this.diff[l]     += val;
    this.diff[r + 1] -= val;
  }

  // Reconstruct the result array — O(n)
  build() {
    const result = [];
    let running = 0;
    for (let i = 0; i < this.diff.length - 1; i++) {
      running += this.diff[i];
      result.push(running);
    }
    return result;
  }
}

// Example: start with [0,0,0,0,0]
const da = new DifferenceArray(5);
da.update(1, 3, 5);  // [0, 5, 5, 5, 0]
da.update(2, 4, 3);  // [0, 5, 8, 8, 3]
console.log(da.build()); // [0, 5, 8, 8, 3]

2D Prefix Sum

Extend the idea to a 2D matrix. prefix[i][j] = sum of all elements in the rectangle from (0,0) to (i−1, j−1).

To compute the sum in rectangle (r1,c1) to (r2,c2):

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

(Inclusion-exclusion: add the big rectangle, subtract the two strips that over-count, add back the corner that was subtracted twice.)

class NumMatrix {
  constructor(matrix) {
    const R = matrix.length, C = matrix[0].length;
    // prefix is (R+1) × (C+1), all zeros
    this.prefix = Array.from({ length: R + 1 }, () => new Array(C + 1).fill(0));

    for (let r = 1; r <= R; r++) {
      for (let c = 1; c <= C; c++) {
        this.prefix[r][c] = matrix[r-1][c-1]
          + this.prefix[r-1][c]
          + this.prefix[r][c-1]
          - this.prefix[r-1][c-1];
      }
    }
  }

  // Sum of rectangle (r1,c1) to (r2,c2), all 0-indexed
  sumRegion(r1, c1, r2, c2) {
    return this.prefix[r2+1][c2+1]
         - this.prefix[r1][c2+1]
         - this.prefix[r2+1][c1]
         + this.prefix[r1][c1];
  }
}

const matrix = [[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]];
const nm = new NumMatrix(matrix);
console.log(nm.sumRegion(2,1,4,3)); // 8
console.log(nm.sumRegion(1,1,2,2)); // 11

Practice Problems

LeetCode 303 — Range Sum Query — Immutable
LeetCode 304 — Range Sum Query 2D — Immutable (2D prefix)
LeetCode 560 — Subarray Sum Equals K
LeetCode 724 — Find Pivot Index
LeetCode 238 — Product of Array Except Self
LeetCode 1480 — Running Sum of 1d Array
LeetCode 370 — Range Addition (difference array)
LeetCode 1094 — Car Pooling (difference array)