Prefix Sum — The Complete Guide

// Build prefix sum array (length n + 1)
const prefix = new Array(nums.length + 1).fill(0);
for (let i = 0; i < nums.length; i++) {
  prefix[i + 1] = prefix[i] + nums[i];
}

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

// Why prefix[0] = 0?
// So that rangeSum(0, j) = prefix[j+1] - prefix[0] = prefix[j+1]
// Without it, you'd need a special case for i = 0.

function countSubarrays(nums: number[], k: number): number {
  const prefixCount = new Map<number, number>();
  prefixCount.set(0, 1); // empty prefix — critical!
  let sum = 0;
  let count = 0;

  for (const num of nums) {
    sum += num;                              // running prefix sum
    count += prefixCount.get(sum - k) ?? 0;  // how many valid starts?
    prefixCount.set(sum, (prefixCount.get(sum) ?? 0) + 1);
  }

  return count;
}

// Why set(0, 1) initially?
// If sum itself equals k, then (sum - k) = 0.
// We need the map to report that the "empty prefix" exists once.
// Without it, we'd miss subarrays starting at index 0.

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

  // Left pass: result[i] = product of all elements to the LEFT of i
  let leftProduct = 1;
  for (let i = 0; i < n; i++) {
    result[i] = leftProduct;
    leftProduct *= nums[i];
  }

  // Right pass: multiply by product of all elements to the RIGHT of i
  let rightProduct = 1;
  for (let i = n - 1; i >= 0; i--) {
    result[i] *= rightProduct;
    rightProduct *= nums[i];
  }

  return result;
}
// Time: O(n) — two passes
// Space: O(1) — result array doesn't count as extra space
// result[i] = leftProduct[i] × rightProduct[i]

function subarraysDivByK(nums: number[], k: number): number {
  const modCount = new Map<number, number>();
  modCount.set(0, 1); // empty prefix has remainder 0
  let sum = 0;
  let count = 0;

  for (const num of nums) {
    sum += num;
    // Handle negative remainders: ((sum % k) + k) % k
    const mod = ((sum % k) + k) % k;
    count += modCount.get(mod) ?? 0;
    modCount.set(mod, (modCount.get(mod) ?? 0) + 1);
  }

  return count;
}
// If prefix[i] % k === prefix[j] % k, then sum(i+1, j) is divisible by k.
// The map counts how many prefix sums share each remainder.

// Build 2D prefix sum
const m = matrix.length, n = matrix[0].length;
const prefix = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

for (let r = 0; r < m; r++) {
  for (let c = 0; c < n; c++) {
    prefix[r + 1][c + 1] =
      matrix[r][c] +
      prefix[r][c + 1] +
      prefix[r + 1][c] -
      prefix[r][c]; // subtract double-counted overlap
  }
}

// Query: sum of rectangle from (r1, c1) to (r2, c2)
function regionSum(r1: number, c1: number, r2: number, c2: number): number {
  return (
    prefix[r2 + 1][c2 + 1] -
    prefix[r1][c2 + 1] -
    prefix[r2 + 1][c1] +
    prefix[r1][c1] // add back double-subtracted corner
  );
}
// Build: O(m × n). Each query: O(1).

Array:  [3,  1,  4,  1,  5,  9,  2,  6]
Index:   0   1   2   3   4   5   6   7

Building prefix (length 9, prefix[0] = 0):
  prefix[0] = 0
  prefix[1] = 0 + 3 = 3
  prefix[2] = 3 + 1 = 4
  prefix[3] = 4 + 4 = 8
  prefix[4] = 8 + 1 = 9
  prefix[5] = 9 + 5 = 14
  prefix[6] = 14 + 9 = 23
  prefix[7] = 23 + 2 = 25
  prefix[8] = 25 + 6 = 31

Prefix: [0, 3, 4, 8, 9, 14, 23, 25, 31]

Query: sum(2, 5) = sum of [4, 1, 5, 9]
  = prefix[6] - prefix[2]
  = 23 - 4
  = 19 ✓ (4 + 1 + 5 + 9 = 19)

Query: sum(0, 3) = sum of [3, 1, 4, 1]
  = prefix[4] - prefix[0]
  = 9 - 0
  = 9 ✓ (3 + 1 + 4 + 1 = 9)

Query: sum(7, 7) = sum of [6]
  = prefix[8] - prefix[7]
  = 31 - 25
  = 6 ✓

Array: [1,  2,  1,  -1,  1,  2]
k = 3

Map starts: {0: 1}  (empty prefix)
sum = 0, count = 0

Step 1: num=1, sum=1
  target = 1 - 3 = -2 → not in map
  map = {0:1, 1:1}  count=0

Step 2: num=2, sum=3
  target = 3 - 3 = 0 → map has 0 with count 1 → count += 1
  map = {0:1, 1:1, 3:1}  count=1
  Found: subarray [1,2] sums to 3 ★

Step 3: num=1, sum=4
  target = 4 - 3 = 1 → map has 1 with count 1 → count += 1
  map = {0:1, 1:1, 3:1, 4:1}  count=2
  Found: subarray [2,1] sums to 3 ★

Step 4: num=-1, sum=3
  target = 3 - 3 = 0 → map has 0 with count 1 → count += 1
  map = {0:1, 1:1, 3:2, 4:1}  count=3
  Found: subarray [1,2,1,-1] sums to 3 ★

Step 5: num=1, sum=4
  target = 4 - 3 = 1 → map has 1 with count 1 → count += 1
  map = {0:1, 1:1, 3:2, 4:2}  count=4
  Found: subarray [2,1,-1,1] sums to 3 ★

Step 6: num=2, sum=6
  target = 6 - 3 = 3 → map has 3 with count 2 → count += 2
  map = {0:1, 1:1, 3:2, 4:2, 6:1}  count=6
  Found: 2 subarrays ending here sum to 3 ★★

Answer: 6

Key insight: the map tells us "how many earlier prefix sums would make
the current subarray sum equal to k?" Each such prefix sum is a valid
starting point for a subarray ending at the current index.

Is the problem about RANGE SUMS or SUBARRAY SUMS?
├── NO  → Not Prefix Sum. Consider Sliding Window, Two Pointers, or DP.
└── YES → Is the array static (no updates between queries)?
          ├── NO  → Use Segment Tree or Binary Indexed Tree instead.
          └── YES → What do you need?
                    ├── Range sum queries → Template 1: Basic prefix array
                    ├── Count subarrays with sum = k → Template 2: Prefix + hash map
                    ├── Product except self → Template 3: Prefix + suffix
                    ├── Divisible by k → Prefix sum modulo k + hash map
                    └── 2D range queries → 2D prefix sum + inclusion-exclusion

What's the key formula?
├── sum(i, j) = prefix[j + 1] − prefix[i]
├── subarray sum = k ↔ prefix[j] − prefix[i] = k ↔ prefix[i] = prefix[j] − k
└── divisible by k ↔ prefix[i] % k === prefix[j] % k