# 31 lines concise and easy understand c++ solution Binary Indexed Tree

• ``````class NumMatrix {
private:
vector<vector<int>> sum;
vector<vector<int>> origin;
int m, n;
public:
NumMatrix(vector<vector<int>> &matrix) {
if(matrix.size() == 0 || matrix[0].size() == 0) return;
m = matrix.size(), n = matrix[0].size();
sum = vector<vector<int>> (m + 1, vector<int>(n + 1, 0));
origin = vector<vector<int>> (m, vector<int>(n, 0));
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
update(i, j, matrix[i][j]);
}
}
}

void update(int row, int col, int val) {
int diff = val - origin[row][col];
origin[row][col] = val;
for(int i = row + 1; i <= m; i += (i & -i)){
for(int j = col + 1; j <= n; j += (j & - j)){
sum[i][j] += diff;
}
}
}

int sumRegion(int row1, int col1, int row2, int col2) {
if(m == 0 || n == 0) return 0;
return getSum(row2 + 1, col2 + 1) + getSum(row1, col1) - getSum(row1, col2  + 1) - getSum(row2 + 1, col1);
}

int getSum(int row, int col){
int res = 0;
for(int i = row; i > 0; i -= (i & -i)){
for(int j = col; j > 0; j -= (j & -j)){
res += sum[i][j];
}
}
return res;
}
};

// Your NumMatrix object will be instantiated and called as such:
// NumMatrix numMatrix(matrix);
// numMatrix.sumRegion(0, 1, 2, 3);
// numMatrix.update(1, 1, 10);
// numMatrix.sumRegion(1, 2, 3, 4);``````

• I like how you used update() in your constructor :). Good job.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.