# Range Sum Query 2D – Mutable

2d fenwick树.

``````class NumMatrix {
int[][] matrix;
int[][] BIT;
int n;
int m;

public int lowbit(int x){
return x & (-x);
}

public void set(int r, int c, int val){
r++;
c++;
for(int i = r; i <= n; i += lowbit(i)){
for(int j = c; j <= m; j += lowbit(j)){
BIT[i][j] += val;
}
}
}
public NumMatrix(int[][] matrix) {
this.matrix = matrix;
this.n = matrix.length;
this.m = matrix[0].length;
this.BIT = new int[n + 1][m + 1];
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
set(i,j,matrix[i][j]);
}
}
}

public void update(int i, int j, int val) {
int diff = val - matrix[i][j];
matrix[i][j] = val;
set(i, j, diff);
}

public int sum(int r, int c) {
int s = 0;
r++;
c++;
for(int i = r; i > 0; i -= lowbit(i)){
for(int j = c; j > 0; j -= lowbit(j)){
s += BIT[i][j];
}
}
return s;
}

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

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