This page explains Java solution to problem Range Sum Query 2D - Mutable
using Binary Indexed Tree
algorithm.
Given a 2D matrix
, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1)
and lower right corner (row2, col2)
.
Input:
matrix = [
[3, 0, 1, 4, 2],
[5, 6, 3, 2, 1],
[1, 2, 0, 1, 5],
[4, 1, 0, 1, 7],
[1, 0, 3, 0, 5]
]
Output:
sumRegion(2, 1, 4, 3) -> 8
update(3, 2, 2)
sumRegion(2, 1, 4, 3) -> 10
package com.vc.hard;
class RangeSumQuery2dMutable {
int m;
int n;
int[][] tree;
int[][] matrix;
public RangeSumQuery2dMutable(int[][] matrix) {
this.m = matrix.length;
if(m == 0) return;
this.n = matrix[0].length;
this.matrix = matrix;
tree = new int[m + 1][n + 1];
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
set(i, j, matrix[i][j]);
}
}
}
public void update(int row, int col, int val) {
if(m == 0 || n == 0) return;
int delta = val - matrix[row][col];
matrix[row][col] = val;
set(row, col, delta);
}
public int sumRegion(int row1, int col1, int row2, int col2) {
return sum(row2 + 1, col2 + 1) + sum(row1, col1) - sum(row1, col2 + 1) - sum(row2 + 1, col1);
}
private void set(int row, int col, int val) {
if(m == 0 || n == 0) return;
for(int i = row + 1; i <= m; i = getNext(i)) {
for(int j = col + 1; j <= n; j = getNext(j)) {
tree[i][j] += val;
}
}
}
private int sum(int row, int col) {
int sum = 0;
if(m == 0 || n == 0) return sum;
for(int i = row; i > 0; i = getParent(i)) {
for(int j = col; j > 0; j = getParent(j)) {
sum += tree[i][j];
}
}
return sum;
}
private int getParent(int x) {
return x - (x & -x);
}
private int getNext(int x) {
return x + (x & -x);
}
}
/**
* Your NumMatrix object will be instantiated and called as such:
* NumMatrix obj = new NumMatrix(matrix);
* obj.update(row,col,val);
* int param_2 = obj.sumRegion(row1,col1,row2,col2);
*/
O(M * N * log(M * N)) to Generate Binary Indexed Tree using Array
O(log (M * N)) to Update element in an input array & Binary Indexed Tree
O(log (M * N)) to Sum elements in an input range Where
M is total number rows in an input array
N is total number cols in an input array
O(M * N) Where
M is total number rows in an input array
N is total number cols in an input array