Range Sum Query 2D - Immutable
Medium 2D prefix sum
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Answer many queries for the sum of a rectangle inside a fixed matrix.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: sum of any rectangle in a fixed grid, fast.
Why this works: P[r][c] holds the sum of everything above and to the left. A rectangle is the big corner sum minus the strip above and the strip to the left, plus the corner that got subtracted twice.
Example: rectangle rows 1..2, cols 1..2
answer = P[3][3] - P[1][3] - P[3][1] + P[1][1](whole) - (top strip) - (left strip) + (top-left corner)
✦Hints open one at a time
↗Approach
Precompute the padded 2D prefix array. The rectangle (r1,c1)–(r2,c2) equals P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]; the last term is added back because it was subtracted twice.
</>Solution (Java)
class NumMatrix {
private final int[][] p;
public NumMatrix(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
p = new int[m + 1][n + 1];
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
p[r + 1][c + 1] = matrix[r][c] + p[r][c + 1] + p[r + 1][c] - p[r][c];
}
public int sumRegion(int r1, int c1, int r2, int c2) {
return p[r2 + 1][c2 + 1] - p[r1][c2 + 1] - p[r2 + 1][c1] + p[r1][c1];
}
}!Common mistake
Forgetting to add back the top-left corner, which was subtracted twice.
- Time: O(m·n) build, O(1) per query.
- Space: O(m·n).
