My Java BIT Solution, 100%

• ``````public class NumMatrix {
// Binary Indexed Tree
int[][] tree;
int[][] sums;
int[][] matrix;
int m, n;
public NumMatrix(int[][] matrix) {
if (matrix.length == 0) {
return;
}
this.m = matrix.length;
this.n = matrix[0].length;
this.tree = new int[m + 1][n + 1];
this.sums = new int[m + 1][n + 1];
this.matrix = matrix;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
sums[i][j] = sums[i - 1][j] + sums[i][j - 1] - sums[i - 1][j - 1] + matrix[i - 1][j - 1];
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
int r = i - (i & -i);
int c = j - (j & -j);
tree[i][j] = sums[i][j] - sums[r][j] - sums[i][c] + sums[r][c];
}
}
}

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

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 row, int col) {
int sum = 0;
for (int i = row; i > 0; i -= (i & -i)) {
for (int j = col; j > 0; j -= (j & -j)) {
sum += tree[i][j];
}
}
return sum;
}
}
``````

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