> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Range Sum Query 2D - Mutable Python Solution

> Tested Python solution for LeetCode 308 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 308, [Medium](/catalog/medium). Topics: [Design](/catalog/topics/design), [Binary Indexed Tree](/catalog/topics/binary-indexed-tree), [Segment Tree](/catalog/topics/segment-tree), [Array](/catalog/topics/array), [Matrix](/catalog/topics/matrix). [View on LeetCode](https://leetcode.com/problems/range-sum-query-2d-mutable/description/).

Generate this problem as a practice environment: tested reference solution, 15 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 308   # by problem number
lcpy gen -s range_sum_query_2d_mutable   # by problem name
```

## Problem

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

### Examples

![Example 1](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/0300-0399/0308.Range%20Sum%20Query%202D%20-%20Mutable/images/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
numMatrix.update(3, 2, 2); // matrix changes from left image to right image
numMatrix.sumRegion(2, 1, 4, 3); // return 10
```

### Constraints

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

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/range_sum_query_2d_mutable/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/range_sum_query_2d_mutable/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class BinaryIndexedTree:
    def __init__(self, n: int) -> None:
        self.n = n
        self.c = [0] * (n + 1)

    @staticmethod
    def lowbit(x: int) -> int:
        return x & -x

    def update(self, x: int, delta: int) -> None:
        while x <= self.n:
            self.c[x] += delta
            x += BinaryIndexedTree.lowbit(x)

    def query(self, x: int) -> int:
        s = 0
        while x > 0:
            s += self.c[x]
            x -= BinaryIndexedTree.lowbit(x)
        return s


class NumMatrix:
    # Time: O(m * n log n) build — one BIT per row
    # Space: O(m * n)
    def __init__(self, matrix: list[list[int]]) -> None:
        self.matrix = matrix
        self.trees = [BinaryIndexedTree(len(row)) for row in matrix]
        for i, row in enumerate(matrix):
            for j, val in enumerate(row):
                self.trees[i].update(j + 1, val)

    # Time: O(log n)
    # Space: O(1)
    def update(self, row: int, col: int, val: int) -> None:
        delta = val - self.matrix[row][col]
        self.matrix[row][col] = val
        self.trees[row].update(col + 1, delta)

    # Time: O(m log n)
    # Space: O(1)
    def sum_region(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return sum(
            self.trees[i].query(col2 + 1) - self.trees[i].query(col1) for i in range(row1, row2 + 1)
        )
```

## Complexity

| Time | Space |
| - | - |
| O(m \* n log n) build — one BIT per row | O(m \* n) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.