# Java 2D Binary-indexed-tree solution 80ms

• For binary indexed tree information, please refer to the Topcoder tutorial:

https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/

The code below is just a 2D version of that. About 80-90 ms run-time in Java.

``````public class NumMatrix {

int[][] tree;
int MaxValRow, MaxValCol;

public NumMatrix(int[][] matrix) {
if (matrix == null || matrix.length == 0)
return;
MaxValRow = matrix.length;
MaxValCol = matrix[0].length;
tree = new int[MaxValRow + 1][MaxValCol + 1];
for (int i = 0; i < MaxValRow; i++) {
for (int j = 0; j < MaxValCol; j++) {
changeSingle(i + 1, j + 1, matrix[i][j]);
}
}
}

public void update(int row, int col, int val) {
changeSingle(row + 1, col + 1, val - readSingle(row + 1, col + 1));
}

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

private int readSum(int row, int col) {
List<Integer> rowList = new ArrayList<Integer>();
List<Integer> colList = new ArrayList<Integer>();
int sum = 0;
while (row > 0){
row -= (row & -row);
}
while (col > 0){
col -= (col & -col);
}
for (Integer i : rowList) {
for (Integer j : colList) {
sum += tree[i][j];
}
}
return sum;
}

private void changeSingle(int row, int col, int val) {
List<Integer> rowList = new ArrayList<Integer>();
List<Integer> colList = new ArrayList<Integer>();
while (row <= MaxValRow) {
row += (row & -row);
}
while (col <= MaxValCol) {
col += (col & -col);
}
for (Integer i : rowList) {
for (Integer j : colList) {
tree[i][j] += val;
}
}
}

private int readSingle(int row, int col) {
int z, rowB = row, colB = col;
List<Integer> rowList = new ArrayList<Integer>();
List<Integer> colList = new ArrayList<Integer>();
z = row - (row & -row);
row--;
while (row != z) {
row -= (row & -row);
}
z = col - (col & -col);
col--;
while (col != z) {
col -= (col & -col);
}
row = rowB; col = colB;
int sum = tree[row][col];
for (Integer j : colList) {
sum -= tree[row][j];
}
for (Integer i : rowList) {
sum -= tree[i][col];
}
for (Integer i : rowList) {
for (Integer j : colList) {
sum += tree[i][j];
}
}
return sum;
}
}``````

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