We can use a 2D Binary Indexed Tree (Fenwick Tree) to efficiently calculate sum in a rectangular area in a mutable 2D matrix.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | public void rangeSum(int[][] inp) { int[][] bit = new int[inp.length + 1][inp[0].length + 1]; for (int i = 0; i < inp.length; i++) for (int j = 0; j < inp[0].length; j++) update(i, j, inp[i][j], bit); } public void update(int i, int j, val, int[][] bit) { int diff = val - inp[i][j]; for (int row = i + 1; row < inp.length; row += row & (-row)) for (int col = j + 1; col < inp[0].length; col += col & (-col)) bit[row][col] += diff; inp[i][j] = val; } public int calcSum(int i, int j) { int sum = 0; for (int row = i + 1; row > 0; row -= row & (-row)) for (int col = j + 1; col > 0; col -= col & (-col)) sum += bit[row][col]; return sum; } public int getSum(int row1, int col1, int row2, int col2) { return calcSum(row2, col2) - calcSum(row1 - 1, col2) - calcSum(row2, col1 - 1) + calcSum(row1 - 1, col1 - 1); } |