Pattern Guide
2D Prefix Sums & Difference Arrays
"O(1) rectangle sum queries. 2D range updates with difference arrays."
2D prefix sums extend the 1D concept to matrices: prefix[i][j] = sum of all elements in rectangle [0..i-1][0..j-1]. Rectangle sum query [r1,c1..r2,c2] in O(1) using inclusion-exclusion. 2D difference arrays enable O(1) range updates on a submatrix. Applications: counting elements in sub-rectangles, matrix maximum sum, number of subarrays with bounded sums.
Problems you can solve with this pattern
4 problems · click any to start solving
// 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];
}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.
// 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];
}- 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.