LeetCode 308. 二维区域和检索 - 可变***

具体思路：

前缀和算区间，后面更新的时候只针对影响的前缀和区间更新；

但是官方采用的是线段树，后面开个专题补一下；

具体代码：

class NumMatrix {
public:
    NumMatrix(vector<vector<int>>& matrix) {
        ma=matrix;
        m=matrix.size();
        n=matrix[0].size();
        dp.resize(m+1,vector<int>(n+1,0));
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                dp[i][j]=matrix[i-1][j-1]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
            }
        }
    }
    
    void update(int row, int col, int val) {
        int temp=ma[row][col];
        ma[row][col]=val;
        temp=val-temp;
        for(int i=row+1;i<=m;i++){
            for(int j=col+1;j<=n;j++){
                dp[i][j]+=temp;
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        return dp[row2+1][col2+1]+dp[row1][col1]-dp[row1][col2+1]-dp[row2+1][col1];
    }
private:
    vector<vector<int>>dp;
    vector<vector<int>>ma;
    int m;
    int n;
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix* obj = new NumMatrix(matrix);
 * obj->update(row,col,val);
 * int param_2 = obj->sumRegion(row1,col1,row2,col2);
 */