# Range Sum Query 2D - Mutable

This page explains Java solution to problem `Range Sum Query 2D - Mutable` using `Binary Indexed Tree` algorithm.

## Problem Statement

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)`.

Example 1:

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

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
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);
*/

``````

## Time Complexity

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

## Space Complexity

O(M * N) Where
M is total number rows in an input array
N is total number cols in an input array