# LeetCode 308: Range Sum Query 2D - Mutable

## Problem Restatement

We are given a 2D integer matrix.

We need to implement a class called `NumMatrix` that supports two operations:

| Operation | Meaning |
|---|---|
| `update(row, col, val)` | Change `matrix[row][col]` to `val` |
| `sumRegion(row1, col1, row2, col2)` | Return the sum of all cells inside the rectangle |

The rectangle is inclusive.

Unlike LeetCode 304, the matrix can change after construction. So a fixed 2D prefix sum matrix is no longer enough.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A 2D integer matrix |
| Update | Change one cell value |
| Query | Sum over an inclusive rectangle |
| Output | Integer sum |
| Goal | Efficient updates and rectangle queries |

Class shape:

```python
class NumMatrix:

    def __init__(self, matrix: list[list[int]]):
        ...

    def update(self, row: int, col: int, val: int) -> None:
        ...

    def sumRegion(
        self,
        row1: int,
        col1: int,
        row2: int,
        col2: int,
    ) -> int:
        ...
```

## Examples

Example matrix:

```python
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],
]
```

Create the object:

```python
obj = NumMatrix(matrix)
```

Query:

```python
obj.sumRegion(2, 1, 4, 3)
```

This rectangle contains:

```text
2 0 1
1 0 1
0 3 0
```

The sum is:

```python
8
```

Now update:

```python
obj.update(3, 2, 2)
```

The cell at row `3`, column `2` changes from `0` to `2`.

Now the same query:

```python
obj.sumRegion(2, 1, 4, 3)
```

The rectangle becomes:

```text
2 0 1
1 2 1
0 3 0
```

The sum is:

```python
10
```

## First Thought: Recompute Each Query Directly

The simplest solution stores the matrix and scans the requested rectangle for each query.

```python
total = 0

for r in range(row1, row2 + 1):
    for c in range(col1, col2 + 1):
        total += matrix[r][c]
```

This gives correct answers.

Updates are easy:

```python
matrix[row][col] = val
```

But each query can cost `O(mn)` in the worst case.

For many operations, this is too slow.

## Why 2D Prefix Sum Is Not Enough

For an immutable matrix, we can build a 2D prefix sum once.

But when one cell changes, many prefix values become stale.

For example, changing one cell near the top-left affects every prefix rectangle that includes it.

That can require updating `O(mn)` prefix entries.

So we need a structure that supports both:

| Operation | Desired |
|---|---:|
| Single-cell update | Fast |
| Rectangle sum | Fast |

## Key Insight

Use a 2D Fenwick Tree.

A 1D Fenwick Tree supports:

| Operation | Time |
|---|---:|
| Point update | `O(log n)` |
| Prefix sum | `O(log n)` |

A 2D Fenwick Tree extends the same idea to matrices:

| Operation | Time |
|---|---:|
| Point update | `O(log m * log n)` |
| Prefix rectangle sum | `O(log m * log n)` |
| Any rectangle sum | `O(log m * log n)` |

The tree stores sums of rectangular regions.

Each update touches a logarithmic number of row indices and a logarithmic number of column indices.

## Coordinate Mapping

The input matrix uses 0-based indexing.

Fenwick Tree uses 1-based indexing internally.

So cell:

```python
(row, col)
```

maps to:

```python
(row + 1, col + 1)
```

This makes the lowbit operations work cleanly.

## 2D Fenwick Update

When a cell changes by `delta`, we add `delta` to every tree node whose rectangle includes that cell.

```python
i = row + 1

while i <= m:
    j = col + 1

    while j <= n:
        tree[i][j] += delta
        j += j & -j

    i += i & -i
```

The inner loop moves across column ranges.

The outer loop moves across row ranges.

## 2D Prefix Sum Query

To get the sum from `(0, 0)` to `(row, col)`, inclusive, move backward through the tree.

```python
total = 0
i = row + 1

while i > 0:
    j = col + 1

    while j > 0:
        total += tree[i][j]
        j -= j & -j

    i -= i & -i
```

This accumulates disjoint rectangles whose union is exactly the prefix rectangle.

## Rectangle Sum Formula

To compute the sum of:

```python
(row1, col1)
```

through:

```python
(row2, col2)
```

use inclusion-exclusion:

```python
sumRegion =
    prefix(row2, col2)
    - prefix(row1 - 1, col2)
    - prefix(row2, col1 - 1)
    + prefix(row1 - 1, col1 - 1)
```

The first prefix contains the whole area from the origin to the bottom-right corner.

Then we subtract the area above and the area to the left.

The top-left overlap was subtracted twice, so we add it back once.

## Algorithm

Initialization:

1. Store matrix dimensions.
2. Store a mutable copy of the matrix.
3. Create a Fenwick tree with size `(m + 1) x (n + 1)`.
4. Insert every matrix value using Fenwick update.

Update:

1. Compute `delta = val - matrix[row][col]`.
2. Store the new value in `matrix`.
3. Add `delta` to the Fenwick tree at `(row, col)`.

Sum query:

1. Compute four prefix rectangle sums.
2. Combine them with inclusion-exclusion.
3. Return the result.

## Correctness

The Fenwick tree stores partial rectangle sums. Each tree cell represents a rectangular block determined by the lowest set bit of its row and column index.

When `update(row, col, val)` changes one matrix value by `delta`, the algorithm adds `delta` to exactly the tree entries whose stored rectangles contain that cell. Therefore, every stored partial rectangle sum remains correct after the update.

The prefix query walks backward through the Fenwick tree using lowest-set-bit jumps. The rectangles collected during this process are disjoint and together cover exactly the rectangle from `(0, 0)` to `(row, col)`. Therefore, the prefix query returns the correct prefix rectangle sum.

For `sumRegion(row1, col1, row2, col2)`, inclusion-exclusion starts with the prefix ending at `(row2, col2)`, removes the rows above `row1`, removes the columns left of `col1`, and adds back the top-left overlap. The remaining cells are exactly the requested rectangle.

Therefore, every update and every rectangle sum query is correct.

## Complexity

| Operation | Time | Space | Why |
|---|---:|---:|---|
| Constructor | `O(mn log m log n)` | `O(mn)` | Insert every cell into the tree |
| `update` | `O(log m log n)` | `O(1)` | Touch logarithmic row and column ancestors |
| `sumRegion` | `O(log m log n)` | `O(1)` | Four prefix queries |

The constructor can also be optimized, but this version is simple and accepted.

## Implementation

```python
class NumMatrix:

    def __init__(self, matrix: list[list[int]]):
        if not matrix or not matrix[0]:
            self.m = 0
            self.n = 0
            self.matrix = []
            self.tree = [[0]]
            return

        self.m = len(matrix)
        self.n = len(matrix[0])

        self.matrix = [[0] * self.n for _ in range(self.m)]
        self.tree = [[0] * (self.n + 1) for _ in range(self.m + 1)]

        for r in range(self.m):
            for c in range(self.n):
                self.update(r, c, matrix[r][c])

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

        i = row + 1

        while i <= self.m:
            j = col + 1

            while j <= self.n:
                self.tree[i][j] += delta
                j += j & -j

            i += i & -i

    def prefix_sum(self, row: int, col: int) -> int:
        if row < 0 or col < 0:
            return 0

        total = 0
        i = row + 1

        while i > 0:
            j = col + 1

            while j > 0:
                total += self.tree[i][j]
                j -= j & -j

            i -= i & -i

        return total

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

## Code Explanation

The constructor handles an empty matrix first.

```python
if not matrix or not matrix[0]:
```

Then it stores dimensions:

```python
self.m = len(matrix)
self.n = len(matrix[0])
```

We keep a separate matrix copy initialized with zeroes:

```python
self.matrix = [[0] * self.n for _ in range(self.m)]
```

This lets us build the Fenwick tree by calling `update`.

```python
for r in range(self.m):
    for c in range(self.n):
        self.update(r, c, matrix[r][c])
```

Inside `update`, compute how much the cell changes.

```python
delta = val - self.matrix[row][col]
```

Then store the new value.

```python
self.matrix[row][col] = val
```

Now update all Fenwick tree entries affected by this cell.

```python
i = row + 1
```

The tree uses 1-based indexing.

The outer loop walks through affected row blocks.

```python
while i <= self.m:
```

The inner loop walks through affected column blocks.

```python
while j <= self.n:
    self.tree[i][j] += delta
    j += j & -j
```

Then move to the next row block.

```python
i += i & -i
```

The `prefix_sum` method returns the sum from `(0, 0)` through `(row, col)`.

If either index is negative, the rectangle is empty.

```python
if row < 0 or col < 0:
    return 0
```

The prefix query moves backward through the Fenwick tree.

```python
while i > 0:
```

For each row block, it also moves backward through column blocks.

```python
while j > 0:
    total += self.tree[i][j]
    j -= j & -j
```

Finally, `sumRegion` combines four prefix sums.

```python
return (
    self.prefix_sum(row2, col2)
    - self.prefix_sum(row1 - 1, col2)
    - self.prefix_sum(row2, col1 - 1)
    + self.prefix_sum(row1 - 1, col1 - 1)
)
```

This isolates exactly the requested rectangle.

## Testing

```python
def run_tests():
    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],
    ]

    obj = NumMatrix(matrix)

    assert obj.sumRegion(2, 1, 4, 3) == 8

    obj.update(3, 2, 2)

    assert obj.sumRegion(2, 1, 4, 3) == 10

    single = NumMatrix([[5]])

    assert single.sumRegion(0, 0, 0, 0) == 5

    single.update(0, 0, 9)

    assert single.sumRegion(0, 0, 0, 0) == 9

    row_matrix = NumMatrix([[1, 2, 3]])

    assert row_matrix.sumRegion(0, 0, 0, 2) == 6

    row_matrix.update(0, 1, 10)

    assert row_matrix.sumRegion(0, 0, 0, 2) == 14

    col_matrix = NumMatrix([
        [1],
        [2],
        [3],
    ])

    assert col_matrix.sumRegion(0, 0, 2, 0) == 6

    col_matrix.update(1, 0, 7)

    assert col_matrix.sumRegion(0, 0, 2, 0) == 11

    negatives = NumMatrix([
        [-1, -2],
        [-3, -4],
    ])

    assert negatives.sumRegion(0, 0, 1, 1) == -10

    negatives.update(0, 1, 5)

    assert negatives.sumRegion(0, 0, 1, 1) == -3

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Standard example | Checks rectangle sum before update |
| Same rectangle after update | Confirms mutable state is reflected |
| Single cell | Smallest matrix |
| One-row matrix | Checks column movement |
| One-column matrix | Checks row movement |
| Negative values | Confirms delta arithmetic |