# solution in java with Fenwich Tree

• public class NumMatrix {
//http://www.hawstein.com/posts/binary-indexed-trees.html
// Fenwick Tree
int[][] Bit;
int[][] matrix;

``````public NumMatrix(int[][] matrix) {
if(matrix == null || matrix.length == 0 || matrix[0].length==0) return;
int row = matrix.length;
int col = matrix[0].length;
Bit = new int[row+1][col+1];
this.matrix = new int[row][col];
for(int i  = 0; i < row; i++) {
for(int j  = 0; j < col; j++) {
update(i, j, matrix[i][j]);
}
}
}

public void update(int row, int col, int val) {
int addi = val - matrix[row][col];
matrix[row][col] = val;
// update fenwich tree data
for(int i = row + 1; i < Bit.length; i+= i&(-i)) {
for(int j = col + 1; j < Bit[0].length; j+= j&(-j)) {
Bit[i][j] += addi;
}
}
}

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

public int getSum(int x, int y) {
int sum = 0;
for(int i = x; i > 0; i-=i&(-i)) {
for(int j = y; j > 0; j-=j&(-j)) {
sum += Bit[i][j];
}
}
return sum;
}
``````

}

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