308

class NumMatrix {
public:
    int rows, cols;
    vector<vector<int>> bit;
    NumMatrix(vector<vector<int>>& matrix) {
        rows = matrix.size();
        cols = matrix[0].size();
        bit.resize(rows+1, vector<int>(cols+1,  0));
        buildBIT(matrix);
    }

    void update(int row, int col, int val) {
        int oldVal = sumRegion(row, col, row, col);
        int diff = val - oldVal;
        updateBIT(row+1, col+1, diff);
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        row1++; col1++; row2++; col2++;
        return query(row2, col2)-query(row2, col1-1)-query(row1-1, col2)+query(row1-1, col1-1);
    }

    void buildBIT(vector<vector<int>>& matrix){
        for(int i=0; i<rows; i++)
            for(int j=0; j<cols; j++)
                updateBIT(i+1, j+1, matrix[i][j]);
    }

    void updateBIT(int row, int col, int val){
        int tcol;
        while(row <= rows){
            tcol = col;
            while(tcol <= cols){
                bit[row][tcol] += val;
                tcol += (tcol & -tcol);
            }
            row += (row & -row);
        }
    }

    int query(int row, int col){
        int tcol, sum=0;
        while(row > 0){
            tcol = col;
            while(tcol > 0){
                sum += bit[row][tcol];
                tcol -= (tcol & -tcol);
            }
            row -= (row & -row);
        }
        return sum;
    }

};

/**
 * 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);
 */