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

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

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

class NumMatrix {
public:
    NumMatrix(vector>& matrix) {
        ma=matrix;
        m=matrix.size();
        n=matrix[0].size();
        dp.resize(m+1,vector(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>dp;
    vector>ma;
    int m;
    int n;
};