Pattern — Prefix Sum

Khi nào dùng

• Range sum query trên static array
• “Subarray sum equals K / divisible by K”
• “Maximum / minimum subarray sum”
• 2D: range sum trên matrix
• Difference array dạng inverse — bulk range update

1D Prefix Sum

// preSum[i] = sum of nums[0..i-1] (length n+1, preSum[0] = 0)
const preSum = [0];
for (let i = 0; i < n; i++) preSum.push(preSum[i] + nums[i]);
 
// Range sum [l..r] inclusive:
const rangeSum = preSum[r + 1] - preSum[l];

1D + HashMap (subarray sum K)

// LC #560 — Subarray Sum Equals K
function subarraySum(nums: number[], k: number): number {
  const map = new Map<number, number>();
  map.set(0, 1);                       // empty prefix
  let sum = 0, count = 0;
  for (const x of nums) {
    sum += x;
    count += map.get(sum - k) ?? 0;    // có bao nhiêu prefix sum = sum-k
    map.set(sum, (map.get(sum) ?? 0) + 1);
  }
  return count;
}

2D Prefix Sum

// preSum[i][j] = sum of matrix[0..i-1][0..j-1]
// Range sum (r1, c1) → (r2, c2):
const sum = preSum[r2+1][c2+1]
          - preSum[r1][c2+1]
          - preSum[r2+1][c1]
          + preSum[r1][c1];   // inclusion-exclusion

Difference Array (inverse pattern)

// Bulk range +val updates trong O(1) per update; sau đó 1 pass để build kết quả.
const diff = new Array(n + 1).fill(0);
function update(l: number, r: number, val: number) {
  diff[l] += val;
  diff[r + 1] -= val;
}
// Sau khi tất cả update:
const result = [];
let curr = 0;
for (let i = 0; i < n; i++) { curr += diff[i]; result.push(curr); }

Top problems

Bài	LC	Pattern
Range Sum Query Immutable	LC #303	1D prefix
Range Sum Query 2D	LC #304	2D prefix
Subarray Sum K	LC #560	Prefix + HashMap
Continuous Subarray Sum	LC #523	Prefix mod K + HashMap
Subarray Sums Divisible by K	LC #974	Same
Max Size Subarray Sum K	LC #325	Prefix + first occurrence
Contiguous Array	LC #525	+1/-1 trick + prefix
Range Addition	LC #370	Difference array
Corporate Flight Bookings	LC #1109	Difference array
Matrix Block Sum	LC #1314	2D prefix
Number of Submatrices Sum to Target	LC #1074	2D + #560 trick

Pitfalls

1. Off-by-one với preSum[i+1] vs preSum[i] — chọn 1 convention rõ ràng.
2. Negative numbers: prefix sum vẫn work, nhưng “max subarray ≤ K” cần cẩn thận.
3. Modular arithmetic: (sum % K + K) % K để xử lý negative mod.
4. HashMap initial state: cần map.set(0, 1) để xử lý prefix bắt đầu từ index 0.

→ Nguồn: 01-Complexity-and-Array, 20-Difference-Array-2D-Prefix