Pattern Reference
2D Prefix Sum
"Prefix sum on 2D grid. Range sum queries, submatrix sum, count submatrices with sum ≤ k."
Loading...
Deep Dive Tutorial
2D prefix sum: pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + grid[i-1][j-1]. Rectangle sum query: pre[r2+1][c2+1] - pre[r1][c2+1] - pre[r2+1][c1] + pre[r1][c1]. 2D difference array: to add v to rectangle [r1,c1..r2,c2], do d[r1][c1]+=v, d[r1][c2+1]-=v, d[r2+1][c1]-=v, d[r2+1][c2+1]+=v. Then take 2D prefix sum to recover the array.
2D prefix sum and rectangle query
// Build 2D prefix sum
function build2DPrefix(grid) {
const m = grid.length, n = grid[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] = grid[i-1][j-1] + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1];
return pre;
}
// Rectangle sum: rows [r1..r2], cols [c1..c2] (0-indexed)
function rectSum(pre, r1, c1, r2, c2) {
return pre[r2+1][c2+1] - pre[r1][c2+1] - pre[r2+1][c1] + pre[r1][c1];
}
// 2D difference array: add val to rectangle [r1..r2][c1..c2]
function addRect(diff, r1, c1, r2, c2, val) {
diff[r1][c1] += val;
diff[r1][c2+1] -= val;
diff[r2+1][c1] -= val;
diff[r2+1][c2+1] += val;
}
// Recover array from 2D difference array
function recover2D(diff) {
const m = diff.length, n = diff[0].length;
for (let i = 0; i < m; i++)
for (let j = 1; j < n; j++) diff[i][j] += diff[i][j-1];
for (let i = 1; i < m; i++)
for (let j = 0; j < n; j++) diff[i][j] += diff[i-1][j];
}Worked Problems
square-dashed
2D prefix sum formula (memorize):
- Build:
- Query [r1,c1..r2,c2]:
2D difference array: For adding v to rectangle, touch all 4 corners with ±v. Recover with row-then-column prefix sums.
Pattern: fix one dimension: Many 2D problems reduce to 1D by fixing row range (left, right columns) and processing column sums. This gives O(n² × 1D_algo) complexity.
- Build:
pre[i][j] = grid[i-1][j-1] + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1]- Query [r1,c1..r2,c2]:
pre[r2+1][c2+1] - pre[r1][c2+1] - pre[r2+1][c1] + pre[r1][c1]2D difference array: For adding v to rectangle, touch all 4 corners with ±v. Recover with row-then-column prefix sums.
Pattern: fix one dimension: Many 2D problems reduce to 1D by fixing row range (left, right columns) and processing column sums. This gives O(n² × 1D_algo) complexity.