Categories
Uncategorized

Range Sum Query 2D Mutable – Java

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

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);
}