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).
Example:
Given matrix = [
[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]
] sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
Note:
- You may assume that the matrix does not change.
- There are many calls to sumRegion function.
- You may assume that row1 ≤ row2 and col1 ≤ col2.
前面一个博文的衍生版本，由原来的一维矩阵变成了现在的二维矩阵，没什么区别，还是先建立和的数组，代码如下所示：
class NumMatrix {
public:
NumMatrix(vector<vector<int>> &matrix){
if(!matrix.size() || !matrix[].size())
return;
sum = vector<vector<int>>(matrix.size(), vector<int>(matrix[].size(), ));
for(int i = ; i < matrix.size(); ++i){
for(int j = ; j < matrix[].size(); ++j){
if(i != && j != ){
sum[i][j] = matrix[i][j] + sum[i][j-] + sum[i-][j] - sum[i-][j-];
}else if(i == && j == ){
sum[i][j] = matrix[i][j];
}else if(i == ){
sum[i][j] = matrix[i][j] + sum[i][j-];
}else{
sum[i][j] = matrix[i][j] + sum[i-][j];
}
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
if(row1 == && col1 == )
return sum[row2][col2];
else if(row1 == )
return sum[row2][col2] - sum[row2][col1-];
else if(col1 == )
return sum[row2][col2] - sum[row1-][col2];
else
return sum[row2][col2] - sum[row2][col1-] - sum[row1-][col2] + sum[row1-][col1-];
}
private:
vector<vector<int>> sum;
};