# 308. Range Sum Query 2D - Mutable

Given a 2D matrix `matrix`, handle multiple queries of the following types:

1. **Update** the value of a cell in `matrix`.
2. Calculate the **sum** of the elements of `matrix` inside the rectangle defined by its **upper left corner** `(row1, col1)` and **lower right corner** `(row2, col2)`.

Implement the NumMatrix class:

* `NumMatrix(int[][] matrix)` Initializes the object with the integer matrix `matrix`.
* `void update(int row, int col, int val)` **Updates** the value of `matrix[row][col]` to be `val`.
* `int sumRegion(int row1, int col1, int row2, int col2)` Returns the **sum** of the elements of `matrix` inside the rectangle defined by its **upper left corner** `(row1, col1)` and **lower right corner** `(row2, col2)`.

**Example 1:**![](https://assets.leetcode.com/uploads/2021/03/14/summut-grid.jpg)

```
Input
["NumMatrix", "sumRegion", "update", "sumRegion"]
[[[[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]]], [2, 1, 4, 3], [3, 2, 2], [2, 1, 4, 3]]
Output
[null, 8, null, 10]

Explanation
NumMatrix numMatrix = new NumMatrix([[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]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (i.e. sum of the left red rectangle)
numMatrix.update(3, 2, 2);       // matrix changes from left image to right image
numMatrix.sumRegion(2, 1, 4, 3); // return 10 (i.e. sum of the right red rectangle)
```

**Constraints:**

* `m == matrix.length`
* `n == matrix[i].length`
* `1 <= m, n <= 200`
* `-105 <= matrix[i][j] <= 105`
* `0 <= row < m`
* `0 <= col < n`
* `-105 <= val <= 105`
* `0 <= row1 <= row2 < m`
* `0 <= col1 <= col2 < n`
* At most `104` calls will be made to `sumRegion` and `update`.

## Solution

In my first idea, I tried the straightforward solution, keep them in a matrix, and sum up all the values in the given range. It works ok. It takes about 30 ms run time.

However, it takes square time complexity to get the range sum.

Then, I came out with another solution is to have an extra matrix keep the range square sum result form \[0,0] to \[i,j]. It can optimally reduce the time of computing the range sum. However, it also makes the update operation less effient. So the time is increasing to 40ms.

Then the final one is the best so far. I just keep the row accumulated result. It share the loading to update and rangeSum. It took only 11 ms.

```java
class NumMatrix {
    int[][] mat;
    int[][] sum;
    int m = 0;
    int n = 0;
    public NumMatrix(int[][] matrix) {
        mat = matrix;
        m = matrix.length;
        n = matrix[0].length;
        sum = new int[m][n];
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                sum[i][j] = matrix[i][j] + (j > 0 ? sum[i][j-1] : 0);
            }
        }
        
    }
    
    public void update(int row, int col, int val) {
        
        for(int j = col; j < n; j++){
            sum[row][j] = sum[row][j] - mat[row][col] + val;
        }
        mat[row][col] = val;
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int ret = 0;
        
        for(int i = row1; i <= row2; i++){
            ret += sum[i][col2] - (col1 > 0 ? sum[i][col1-1] : 0);
        }
        return ret;
    }
}

```
