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 {
private: vector<vector<int>> dp;
public: NumMatrix(vector<vector<int>>& matrix) {
dp.resize(matrix.size() + 1, vector<int>(matrix[0].size() + 1));
for (int i = 1;
i <= matrix.size();
i++) {
for (int j = 1;
j <= matrix[0].size();
j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + matrix[i - 1][j - 1];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
return dp[row2 + 1][col2 + 1] - dp[row2 + 1][col1] - dp[row1][col2 + 1] + 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?
