Range Sum Query 2D
Given a 2D matrix `matrix`, find the sum of the elements inside the rectangle defined by its upper left corner `(row1, col1)` and lower right corner `(row2, col2)`.
Constraints:
- 1 <= matrix.length <= 200
- 1 <= matrix[0].length <= 200
- 0 <= row1 <= row2 < matrix.length
- 0 <= col1 <= col2 < matrix[0].length
Examples:
Input: [[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]
Output: 8
Explanation: Sum of elements in the rectangle from (2, 1) to (4, 3) is 8 (i.e., 1 + 7 + 0).
Solutions
Prefix Sum
We use a prefix sum array `dp` where `dp[i][j]` is the sum of all elements in the rectangle from `(0, 0)` to `(i - 1, j - 1)`. We can then calculate the sum of the elements in the rectangle from `(row1, col1)` to `(row2, col2)` as `dp[row2 + 1][col2 + 1] - dp[row2 + 1][col1] - dp[row1][col2 + 1] + dp[row1][col1]`.
class NumMatrix {
constructor(matrix) {
this.dp = Array(matrix.length + 1)
.fill(0)
.map(() => Array(matrix[0].length + 1).fill(0));
for (let i = 1; i <= matrix.length; i++) {
for (let j = 1; j <= matrix[0].length; j++) {
this.dp[i][j] =
this.dp[i - 1][j] +
this.dp[i][j - 1] -
this.dp[i - 1][j - 1] +
matrix[i - 1][j - 1];
}
}
}
sumRegion(row1, col1, row2, col2) {
return (
this.dp[row2 + 1][col2 + 1] -
this.dp[row2 + 1][col1] -
this.dp[row1][col2 + 1] +
this.dp[row1][col1]
);
}
}
Follow-up:
What if the matrix is very large and we need to query the sum of the elements in the rectangle many times?
