## Range Sum Query 2D - Mutable

• Time:O(mn\log mn)
• Space:O(mn)

## C++

``````class FenwickTree {
public:
FenwickTree(int m, int n) : sums(m + 1, vector<int>(n + 1)) {}

void update(int row, int col, int delta) {
for (int i = row; i < sums.size(); i += i & -i)
for (int j = col; j < sums[0].size(); j += j & -j)
sums[i][j] += delta;
}

int get(int row, int col) {
int sum = 0;
for (int i = row; i > 0; i -= i & -i)
for (int j = col; j > 0; j -= j & -j)
sum += sums[i][j];
return sum;
}

private:
vector<vector<int>> sums;
};

class NumMatrix {
public:
NumMatrix(vector<vector<int>>& matrix)
: matrix(matrix), tree(matrix.size(), matrix[0].size()) {
for (int i = 0; i < matrix.size(); ++i)
for (int j = 0; j < matrix[0].size(); ++j)
tree.update(i + 1, j + 1, matrix[i][j]);
}

void update(int row, int col, int val) {
tree.update(row + 1, col + 1, val - matrix[row][col]);
matrix[row][col] = val;
}

int sumRegion(int row1, int col1, int row2, int col2) {
return tree.get(row2 + 1, col2 + 1) - tree.get(row1, col2 + 1) -
tree.get(row2 + 1, col1) + tree.get(row1, col1);
}

private:
vector<vector<int>> matrix;
FenwickTree tree;
};
``````

## JAVA

``````class FenwickTree {
public FenwickTree(int m, int n) {
sums = new int[m + 1][n + 1];
}

public void update(int row, int col, int delta) {
for (int i = row; i < sums.length; i += i & -i)
for (int j = col; j < sums[0].length; j += j & -j)
sums[i][j] += delta;
}

public int get(int row, int col) {
int sum = 0;
for (int i = row; i > 0; i -= i & -i)
for (int j = col; j > 0; j -= j & -j)
sum += sums[i][j];
return sum;
}

private int[][] sums;
}

class NumMatrix {
public NumMatrix(int[][] matrix) {
this.matrix = matrix;
tree = new FenwickTree(matrix.length, matrix[0].length);
for (int i = 0; i < matrix.length; ++i)
for (int j = 0; j < matrix[0].length; ++j)
tree.update(i + 1, j + 1, matrix[i][j]);
}

public void update(int row, int col, int val) {
tree.update(row + 1, col + 1, val - matrix[row][col]);
matrix[row][col] = val;
}

public int sumRegion(int row1, int col1, int row2, int col2) {
return tree.get(row2 + 1, col2 + 1) - tree.get(row1, col2 + 1) - tree.get(row2 + 1, col1) +
tree.get(row1, col1);
}

private int[][] matrix;
private FenwickTree tree;
}
``````

## Python

``````class FenwickTree:
def __init__(self, m: int, n: int):
self.sums = [[0] * (n + 1) for _ in range(m + 1)]

def update(self, row: int, col: int, delta: int) -> None:
i = row
while i < len(self.sums):
j = col
while j < len(self.sums[0]):
self.sums[i][j] += delta
j += j & -j
i += i & -i

def get(self, row: int, col: int) -> int:
sum = 0
i = row
while i > 0:
j = col
while j > 0:
sum += self.sums[i][j]
j -= j & -j
i -= i & -i
return sum

class NumMatrix:
def __init__(self, matrix: List[List[int]]):
self.matrix = matrix
self.tree = FenwickTree(len(matrix), len(matrix[0]))

for i in range(len(matrix)):
for j, val in enumerate(matrix[i]):
self.tree.update(i + 1, j + 1, val)

def update(self, row: int, col: int, val: int) -> None:
self.tree.update(row + 1, col + 1, val - self.matrix[row][col])
self.matrix[row][col] = val

def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
return self.tree.get(row2 + 1, col2 + 1) - self.tree.get(row1, col2 + 1) - \
self.tree.get(row2 + 1, col1) + self.tree.get(row1, col1)
``````