1.区域和检索:
简单题，前缀和方法
乍一看就觉得应该用前缀和来做，一个数组多次查询。
实现方法: 新建一个private数组prefix_sum[i]，用来存储nums前i个数组的和，
需要找区间和的时候直接通过prefix_sum[j]-prefix[i-1]即可得到从[i,j]区间的和，当i是0的时候需要特殊处理以防数组越界。
1 class NumArray { 2 public: 3 NumArray(vector<int> nums) { 4 prefix_sum.reserve(nums.size()); 5 int sum = 0; 6 for(int i: nums) { 7 sum+=i; 8 prefix_sum.push_back(sum); 9 } 10 } 11 12 int sumRange(int i, int j) { 13 if(i == 0) return prefix_sum[j]; 14 return prefix_sum[j]-prefix_sum[i-1]; 15 } 16 private: 17 vector<int> prefix_sum; 18 };
那我们来看一下，若是方阵的情况怎么办？
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条件筛掉就行了，细节观察注释。
1 class NumMatrix { 2 private: vector<vector<int>>dp; 3 public: 4 NumMatrix(vector<vector<int>> matrix) { 5 dp=matrix; 6 int n=matrix.size(); 7 if(n>0){ 8 /*求和，先从左往右叠加
