39ms Concise and Easy understanding C++ Binary Index Tree Solution, beating 89%

• This solution comes from 2D Binary Index Tree. You can refer to Topcoder or GeekforGeek website for explanations.

``````class NumMatrix {
int _nrow = 0;
int _ncol = 0;
vector<vector<int>> _matrix;
vector<vector<int>> _bit;

void add(int row, int col, int val) {
++row;
++col;
while(row <= _nrow) {
int colIdx = col;
while(colIdx <= _ncol) {
_bit[row][colIdx] += val;
colIdx += (colIdx&(-colIdx));
}
row += (row&(-row));
}
}

int region(int row, int col) {
++row;
++col;
int res = 0;
while(row > 0) {
int colIdx = col;
while(colIdx > 0) {
res += _bit[row][colIdx];
colIdx -= (colIdx & (-colIdx));
}
row -= (row & (-row));
}
return res;
}

public:
NumMatrix(vector<vector<int>> &matrix) {
if (!matrix.size() || !matrix[0].size()) return;
_nrow = matrix.size();
_ncol = matrix[0].size();
_matrix = matrix;
_bit = vector<vector<int>> (_nrow+1, vector<int>(_ncol+1, 0));
for (int i = 0; i < _nrow; ++i)
for (int j = 0; j < _ncol; ++j)
}

void update(int row, int col, int val) {
int diff = val - _matrix[row][col];
if (diff) {