1.区域和检索:
简单题，前缀和方法
乍一看就觉得应该用前缀和来做，一个数组多次查询。
实现方法: 新建一个private数组prefix_sum[i]，用来存储nums前i个数组的和，
需要找区间和的时候直接通过prefix_sum[j]-prefix[i-1]即可得到从[i,j]区间的和，当i是0的时候需要特殊处理以防数组越界。
class NumArray {
public:
NumArray(vector<int> nums) {
prefix_sum.reserve(nums.size());
int sum = ;
for(int i: nums) {
sum+=i;
prefix_sum.push_back(sum);
}
}
int sumRange(int i, int j) {
if(i == ) return prefix_sum[j];
return prefix_sum[j]-prefix_sum[i-];
}
private:
vector<int> prefix_sum;
};
那我们来看一下，若是方阵的情况怎么办？
2.二维区域和检索
解决方法一样，不同点在于如何求和和如何通过前缀和获得解。
二维的从(row1,col1)~(row2,col2)的求和情况应该是
dp[row2][col2]+dp[row1-1][col1-1]-dp[row2][col1-1]-dp[row1-1][col2]
这个需要我们的一点点初中数学的知识，加的dp[row1][col1-1]是被重复删去的区间，所以要加回来。
同样，要避开那些边界特殊情况，直接用if条件筛掉就行了，细节观察注释。
class NumMatrix {
private: vector<vector<int>>dp;
public:
NumMatrix(vector<vector<int>> matrix) {
dp=matrix;
int n=matrix.size();
if(n>){
/*求和，先从左往右叠加*/
int m=matrix[].size();
for(int i=;i<n;i++)
for(int j=;j<m;j++)
dp[i][j]+=dp[i][j-];
/*再从上往下叠加*/
for(int i=;i<n;i++)
for(int j=;j<m;j++)
dp[i][j]+=dp[i-][j];
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
/*最特殊的情况:row1=0,col1=0*/
if(row1==&&col1==)return dp[row2][col2];
/*特殊情况1:row1=0但col1!=0*/
if(row1==){
return dp[row2][col2]-dp[row2][col1-];
}
/*特殊情况2:row1!=0但col1=0*/
else if(col1==){
return dp[row2][col2]-dp[row1-][col2];
}
/*正常情况:row1不等于0同时colq也不等于0*/
else{
return dp[row2][col2]+dp[row1-][col1-]-dp[row2][col1-]-dp[row1-][col2];
}
}
};
/**
* Your NumMatrix object will be instantiated and called as such:
* NumMatrix obj = new NumMatrix(matrix);
* int param_1 = obj.sumRegion(row1,col1,row2,col2);
*/