> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0308-range-sum-query-2d-mutable.md).

# 0308. Range Sum Query 2D - Mutable

<https://leetcode.com/problems/range-sum-query-2d-mutable>

## Description

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

## ac1: plain pre-sum

Notice:

* matrix cannot use `clone()`, the array is Object, so it's shallow copy
* be careful handling first row, out of boundary exception.

```java
class NumMatrix {
    int[][] matrix, sumMatrix;

    public NumMatrix(int[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return;

        this.matrix = matrix;
        int row = matrix.length;
        int col = matrix[0].length;

        this.sumMatrix = new int[row][col];
        for(int c = 0; c < col; c++) {
            sumMatrix[0][c] = matrix[0][c];
        }
        for (int r = 1; r < row; r++) {
            for (int c = 0; c < col; c++) {
                sumMatrix[r][c] = sumMatrix[r-1][c] + matrix[r][c];
            }
        }
    }

    public void update(int row, int col, int val) {
        int diff = val - matrix[row][col];
        matrix[row][col] = val;
        for (int r = row; r < sumMatrix.length; r++) {
            sumMatrix[r][col] += diff;
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;

        for (int c = col1; c <= col2; c++) {
            if (row1 == 0) {
                sum += sumMatrix[row2][c];
            } else {
                sum += sumMatrix[row2][c] - sumMatrix[row1-1][c];
            }
        }
        return sum;
    }
}

/**
 * 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);
 */
```

## ac2: Binary Indexed Tree

```java
class NumMatrix {
    int[][] matrix, bit;

    public NumMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return;
        this.matrix = matrix;
        int row = matrix.length;
        int col = matrix[0].length;

        bit = new int[row+1][col+1];
        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                int val = matrix[r][c];
                matrix[r][c] = 0;
                update(r, c, val);
            }
        }
    }

    public void update(int row, int col, int val) {
        int diff = val - matrix[row][col];
        matrix[row][col] = val;
        for (int r = row+1; r < bit.length; r += r & -r) {
            for (int c = col+1; c < bit[0].length; c += c & -c) {
                bit[r][c] += diff;
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return getSum(row2, col2) - getSum(row1-1, col2) - getSum(row2, col1-1) + getSum(row1-1, col1-1);

    }
    private int getSum(int row, int col) {
        int sum = 0;
        for (int r = row+1; r > 0; r -= r & -r) {
            for (int c = col+1; c > 0; c -= c & -c) {
                sum += bit[r][c];
            }
        }
        return sum;
    }
}

/**
 * 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);
 */
```

![](https://raw.githubusercontent.com/hot13399/leetcode-graphic-answer/master/308.%20Range%20Sum%20Query%202D%20-%20Mutable.jpg)