304. Range Sum Query 2D - Immutable

[namespace-io]

2D树状数组
https://www.topcoder.com/community/competitive-programming/tutorials/binary-indexed-trees/

class NumMatrix {
private:
    vector<vector<int>> arr;
    vector<vector<int>> sum;
    int row;
    int col;
public:
    NumMatrix(vector<vector<int>>& matrix) {
        if(matrix.empty() || matrix.empty()) return;
        row = matrix.size();
        col = matrix[0].size();
        
        arr.resize(row + 1, vector<int>(col + 1, 0));
        sum.resize(row + 1, vector<int>(col + 1, 0));
        for(int i = 1; i <= row; i++){
            for(int j = 1; j <= col; j++){
                update(i, j, matrix[i-1][j-1]);
            }
        }
         
    }
    
    void update(int x, int y, int v){
        int oldval = arr[x][y];
        for(int i = x; i <= row; i += lowbit(i)){
            for(int j = y; j <= col; j += lowbit(j)){
                sum[i][j] = sum[i][j] + v - oldval; 
            }
        }
        
        arr[x][y] = v;
    }
    
    int getsum(int x, int y){
        int ret = 0;
        for(int i = x; i > 0; i -= lowbit(i)){
            for(int j = y; j > 0; j -= lowbit(j)){
                ret = ret + sum[i][j];
            }
        }
        
        return ret;
    }
    int lowbit(int i){ return i & -i;}
    int sumRegion(int row1, int col1, int row2, int col2) {
        
        return getsum(row2 + 1,col2 + 1) - getsum(row1,col2 + 1) - getsum(row2 + 1,col1) + getsum(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);
 */

动态规划
dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + matrix[i-1][j-1];求[0,0]到[i-1][j-1]矩阵和

class NumMatrix {
private:
    vector<vector<int>> dp;
public:
    NumMatrix(vector<vector<int>>& matrix) {
        if(matrix.empty() || matrix.empty()) return;
        int m = matrix.size();
        int 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] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + matrix[i-1][j-1];
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        return dp.empty() ? 0 : (dp[row2 + 1][col2 + 1] - dp[row1][col2 + 1] - dp[row2 + 1][col1] + dp[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);
 */

用整个矩形的减去一个风车

class NumMatrix {
public:
    
    vector<vector<int>> a;
    vector<vector<int>> b;
    vector<vector<int>> c;
    vector<vector<int>> d;
    int m;
    int n;
    int sum;
    NumMatrix(vector<vector<int>>& matrix) {
        m = 0;
        n = 0;
        m = matrix.size();
        if(m != 0) n = matrix[0].size();
        
        
        a.resize(m + 2, vector<int>(n + 2 , 0));
        b.resize(m + 2, vector<int>(n + 2 , 0));
        c.resize(m + 2, vector<int>(n + 2 , 0));
        d.resize(m + 2, vector<int>(n + 2 , 0));
       
        
        sum = 0;
        if(m != 0 && n != 0){
            for(int i = 1; i <= m; i++){
                int line = 0;
                for(int j = 1; j <= n; j++){
                    line += matrix[i-1][j-1];
                    a[i][j] = a[i-1][j] + line;
                }

                sum += line;
            }


            for(int i = m; i >= 1; i--){
                int line = 0;
                for(int j = 1; j <= n; j++){
                    line += matrix[i-1][j-1];
                    b[i][j] = b[i+1][j] + line;
                }
            }


            for(int i = 1; i <= m; i++){
                int line = 0;
                for(int j = n; j >= 1; j--){
                    line += matrix[i-1][j-1];
                    c[i][j] = c[i-1][j] + line;
                }
            }


            for(int i = m; i >= 1; i--){
                int line = 0;
                for(int j = n; j >= 1; j--){
                    line += matrix[i-1][j-1];
                    d[i][j] = d[i+1][j] + line;
                }
            }
        }
        
        

        
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        return (m != 0 && n != 0) ? sum - (a[row2+1][col1] + b[row2 + 2][col2 + 1] + d[row1 + 1][col2 + 2] + c[row1][col1 + 1] ) : 0;
    }
};

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