https://leetcode-cn.com/problems/range-sum-query-2d-immutable/
思路:二维前缀和,查询时可以把区域划分为四块,
O
(
n
m
)
O(nm)
O(nm)初始化,
O
(
1
)
O(1)
O(1)查询。
class NumMatrix {
public:
vector<vector<int>> sum;
NumMatrix(vector<vector<int>>& matrix) {
int n=matrix.size();
if(!n)
return;
int m=matrix[0].size();
vector<vector<int>> tmp_sum(n+1,vector<int>(m+1));
for(int i=1;i<=n;i++)
{
tmp_sum[i][1]=matrix[i-1][0];
for(int j=2;j<=m;j++)
tmp_sum[i][j]=tmp_sum[i][j-1]+matrix[i-1][j-1];
for(int j=1;j<=m;j++)
tmp_sum[i][j]+=tmp_sum[i-1][j];
}
sum=move(tmp_sum);
}
int sumRegion(int row1, int col1, int row2, int col2) {
return sum[row2+1][col2+1]-sum[row1][col2+1]-sum[row2+1][col1]+sum[row1][col1];
}
};
/**
* Your NumMatrix object will be instantiated and called as such:
* NumMatrix* obj = new NumMatrix(matrix);
* int param_1 = obj->sumRegion(row1,col1,row2,col2);
*/