308. Range Sum Query 2D Mutable - cocoder39/coco39_LC GitHub Wiki

class NumMatrix {
public:
    NumMatrix(vector<vector<int>> &matrix) : copy(matrix){
        _row = matrix.size();
        if (_row == 0) return;
        _col = matrix[0].size();

        tree = vector<vector<int>>(_row + 1, vector<int>(_col + 1));
        for (int i = 0; i < _row; i++) //O(n^2 * (logn)^2)
         for (int j = 0; j < _col; j++) {
            add(i, j, matrix[i][j]);
        }
    }

    void update(int row, int col, int val) { //O((logn)^2)
        int inc = val - copy[row][col];
        if (inc == 0)   return;
        copy[row][col] = val;
        add(row, col, inc);
    }

    int sumRegion(int row1, int col1, int row2, int col2) { //O((logn)^2)
        return cum(row2, col2) - cum(row1 - 1, col2) - cum(row2, col1 - 1) + cum(row1 - 1, col1 - 1);
    }
private:
    void add(int row, int col, int val) { //O((log n)^2)
        for (int i = row + 1; i <= _row; i += i & (-i)) 
          for (int j = col + 1; j <= _col; j += j & (-j)) {
                tree[i][j] += val;
        }
    }
    
    int cum(int row, int col) { //O((log n)^2)
        int sum = 0;
        for (int i = row + 1; i > 0; i -= i & (-i))
         for (int j = col + 1; j > 0; j -= j & (-j)) {
                sum += tree[i][j];
        }
        return sum;
    }
    
    vector<vector<int>> tree;
    vector<vector<int>> copy;
    int _row;
    int _col;
};