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:

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

Class shape:

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:

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:

obj = NumMatrix(matrix)

Query:

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

This rectangle contains:

2 0 1
1 0 1
0 3 0

The sum is:

8

Now update:

obj.update(3, 2, 2)

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

Now the same query:

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

The rectangle becomes:

2 0 1
1 2 1
0 3 0

The sum is:

10

First Thought: Recompute Each Query Directly

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

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:

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:

Key Insight

Use a 2D Fenwick Tree.

A 1D Fenwick Tree supports:

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

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:

(row, col)

maps to:

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

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.

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:

(row1, col1)

through:

(row2, col2)

use inclusion-exclusion:

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

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

Implementation

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.

if not matrix or not matrix[0]:

Then it stores dimensions:

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

We keep a separate matrix copy initialized with zeroes:

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

This lets us build the Fenwick tree by calling update.

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.

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

Then store the new value.

self.matrix[row][col] = val

Now update all Fenwick tree entries affected by this cell.

i = row + 1

The tree uses 1-based indexing.

The outer loop walks through affected row blocks.

while i <= self.m:

The inner loop walks through affected column blocks.

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

Then move to the next row block.

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.

if row < 0 or col < 0:
    return 0

The prefix query moves backward through the Fenwick tree.

while i > 0:

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

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

Finally, sumRegion combines four prefix sums.

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

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: