Here’s a hard LC problem which is actually just a variation of the Range Sum Query problem but instead, you have to work on a 2D data.
In the Range Sum Query problem, whether it’s immutable or mutable, you can solve the problem using Fenwick or Binary Index Tree. Similarly, this hard problem can also be solved by using Fenwick Tree. So the idea is, we’ll use a 2-dimensional array which will hold multiple Fenwick trees: one for each row of the matrix.
The solution is almost similar to the Range Sum Query 1D and the only thing that we have to consider is that now, we need to know which row of the matrix to operate to. Remember, each row will have it’s own Fenwick Tree.
class NumMatrix {
private int[][] tree;
private int[][] matrix;
public NumMatrix(int[][] matrix) {
this.matrix = matrix;
if(matrix.length == 0 || matrix[0].length == 0) return;
tree = new int[matrix.length][matrix[0].length + 1];
// create the tree
for(int row=0; row < matrix.length; row++){
for(int col=0; col < matrix[0].length; col++){
updateTree(tree[row], col, matrix[row][col]);
}
}
}
private void updateTree(int[] row, int column, int value){
column++;
while(column < row.length) {
row[column] += value;
column += column & -column;
}
}
public void update(int row, int col, int val) {
int diff = val - matrix[row][col];
matrix[row][col] = val;
updateTree(tree[row], col, diff);
}
private int prefixSum(int row, int column){
int sum = 0;
column++;
while(column > 0){
sum += tree[row][column];
column -= column & -column;
}
return sum;
}
public int sumRegion(int row1, int col1, int row2, int col2) {
int sum = 0;
while(row2 >= row1){
sum += prefixSum(row2, col2) - prefixSum(row2, col1 - 1);
row2--;
}
return sum;
}
}
Runtime: 12 ms, faster than 90.78% of Java online submissions for Range Sum Query 2D - Mutable.
Memory Usage: 47.3 MB, less than 7.14% of Java online submissions for Range Sum Query 2D - Mutable.