BiruLyu
5/22/2017 - 5:47 AM

## 308. Range Sum Query 2D - Mutable.java

``````public class NumMatrix {
private int[][] nums;
private int[][] BITree;
private int m;
private int n;

public NumMatrix(int[][] matrix) {

//if (matrix==null||matrix.length == 0 || matrix[0].length == 0) return;//["NumMatrix"] [[[]]]
if (matrix==null||matrix.length == 0) return;
this.m = matrix.length;// row num
this.n = matrix[0].length;
this.nums = new int[this.m][this.n];
this.BITree = new int[this.m + 1][this.n + 1];

for (int i = 0; i < this.m; i++){
for (int j = 0; j < this.n; j++){
update(i, j, matrix[i][j]);
}
}

}

public void update(int row, int col, int val) {
if (m == 0 || n == 0) return;
//if (this.m == 0 || this.n == 0) return; //["NumMatrix"] [[[]]]
int diff = val - nums[row][col];
nums[row][col] = val;

for(int i = row + 1; i <= this.m; i += i & (-i)){
for(int j = col + 1; j <= this.n; j += j & (-j)){
BITree[i][j] += diff;
}
}
}

public int getSum(int row, int col){
if (m == 0 || n == 0) return 0;
int sum = 0;

for(int i = row + 1; i > 0; i -= i & (-i)){
for(int j = col + 1; j > 0; j -= j & (-j)){
sum += BITree[i][j];
}
}

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

return getSum(row2,col2) - getSum(row1 - 1, col2) - getSum(row2, col1 - 1) + getSum(row1 - 1 ,col1 - 1);
}
}

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