LeetCode 308: Range Sum Query 2D - Mutable Solution in Python – A Step-by-Step Guide

What Is LeetCode 308: Range Sum Query 2D - Mutable?

In LeetCode 308: Range Sum Query 2D - Mutable, you’re given a 2D matrix, and you need to create a data structure that supports two operations: updating any cell and computing the sum of any rectangular submatrix. For example, with a matrix [[3, 0, 1], [5, 6, 3], [1, 2, 1]], you might update (1, 1) to 4 and then query the sum of rows 0-2, cols 0-2 (getting 21). This problem extends LeetCode 307: Range Sum Query - Mutable into two dimensions, adding complexity and fun.

Problem Statement

• Input: A 2D integer matrix matrix and method calls:
• NumMatrix(matrix): Initialize with the matrix.
• update(row, col, val): Update matrix[row][col] to val.
• sumRegion(row1, col1, row2, col2): Return sum of rectangle from (row1, col1) to (row2, col2).
• Output: Sum for each sumRegion call; no explicit return for update.
• Rules: Indices are 0-based and within bounds.

Constraints

• 1 <= m, n <= 200 (rows m, cols n)
• -10⁹ <= matrix[row][col] <= 10⁹
• 0 <= row < m, 0 <= col < n
• -10⁹ <= val <= 10⁹
• 0 <= row1 <= row2 < m, 0 <= col1 <= col2 < n
• At most 10⁴ calls to update and sumRegion.

Examples

• Input: ["NumMatrix","sumRegion","update","sumRegion"], [[[[3,0,1],[5,6,3],[1,2,1]]],[0,0,2,2],[1,1,4],[0,0,2,2]]
• Output: [null, 22, null, 20]
• Init: [[3, 0, 1], [5, 6, 3], [1, 2, 1]]
• Sum(0,0,2,2): 3+0+1+5+6+3+1+2+1 = 22
• Update(1,1,4): [[3, 0, 1], [5, 4, 3], [1, 2, 1]]
• Sum(0,0,2,2): 3+0+1+5+4+3+1+2+1 = 20
• Input: ["NumMatrix","sumRegion"], [[[[1,2],[3,4]]],[0,0,1,1]]
• Output: [null, 10]

Understanding the Problem: 2D Dynamic Range Sums

To solve LeetCode 308: Range Sum Query 2D - Mutable in Python, we need a class that initializes with a 2D matrix and efficiently handles updates and region sum queries. A naive approach—updating the matrix and summing each query—takes O(m*n) per query, far too slow. Instead, we’ll use:

• Best Solution (2D BIT): O(m*n) build, O(log m * log n) update/query, O(m*n) space—compact and fast.
• Alternative Solution (2D Segment Tree): O(m*n) build, O(log m * log n) update/query, O(m*n) space—structured and clear.

Let’s start with the 2D BIT, explained in a beginner-friendly way.

Best Solution: 2D Binary Indexed Tree (BIT)

Why This Is the Best Solution

The 2D Binary Indexed Tree is the top pick for LeetCode 308 because it’s efficient—O(log m * log n) for updates and queries—and uses O(m*n) space with a minimalist design. It extends the 1D BIT from LeetCode 307 to two dimensions, using bit operations to manage cumulative sums across rows and columns. It’s like a lightweight 2D calculator—perfect for speed and simplicity!

How It Works

Think of a 2D BIT as a grid of partial sums:

• Step 1: Build the BIT:
• Each cell (i, j) stores the sum of a rectangular region ending at (i-1, j-1), adjusted via bit operations.
• Step 2: Update:
• Add a difference to all affected BIT cells using LSB (least significant bit) in both dimensions.
• Step 3: Query:
• Compute a region sum using inclusion-exclusion on prefix sums.
• Step 4: Why It Works:
• Logarithmic updates/queries due to binary indexing.
• Prefix sums enable fast region calculations.

It’s like a 2D sum tracker with a clever twist!

Step-by-Step Example

Example: matrix = [[3, 0], [5, 6]]

• Build:
• BIT (1-based): [[0, 0, 0], [0, 3, 3], [0, 8, 14]]
• BIT[1][1] = 3, BIT[2][1] = 8 (3+5), BIT[2][2] = 14 (3+0+5+6).
• SumRegion(0, 0, 1, 1):
• Prefix(2,2) - Prefix(0,2) - Prefix(2,0) + Prefix(0,0) = 14 - 0 - 0 + 0 = 14.
• Update(1, 1, 4):
• Diff = 4-6 = -2, update BIT: [[0, 0, 0], [0, 3, 3], [0, 8, 12]].
• SumRegion(0, 0, 1, 1):
• 12 - 0 - 0 + 0 = 12.

Code with Detailed Line-by-Line Explanation

Copy codeclass NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        self.m, self.n = len(matrix), len(matrix[0])
        self.matrix = matrix
        self.bit = [[0] * (self.n + 1) for _ in range(self.m + 1)]
        # Build BIT
        for i in range(self.m):
            for j in range(self.n):
                self._update_bit(i + 1, j + 1, matrix[i][j])

    def _update_bit(self, row: int, col: int, val: int):
        i = row
        while i <= self.m:
            j = col
            while j <= self.n:
                self.bit[i][j] += val
                j += j & (-j)  # Next col via LSB
            i += i & (-i)  # Next row via LSB

    def _get_sum(self, row: int, col: int):
        sum = 0
        i = row
        while i > 0:
            j = col
            while j > 0:
                sum += self.bit[i][j]
                j -= j & (-j)  # Prev col via LSB
            i -= i & (-i)  # Prev row via LSB
        return sum

    def update(self, row: int, col: int, val: int) -> None:
        diff = val - self.matrix[row][col]
        self.matrix[row][col] = val
        self._update_bit(row + 1, col + 1, diff)

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        # Inclusion-exclusion for rectangle sum
        return (self._get_sum(row2 + 1, col2 + 1) - 
                self._get_sum(row1, col2 + 1) - 
                self._get_sum(row2 + 1, col1) + 
                self._get_sum(row1, col1))

• Init: O(m*n)
• Lines 5-9: Build BIT with original values.
• _update_bit: O(log m * log n)
• Lines 11-17: Update all affected cells.
• _get_sum: O(log m * log n)
• Lines 19-27: Compute prefix sum.
• Update: O(log m * log n)
• Lines 29-31: Adjust BIT with difference.
• SumRegion: O(log m * log n)
• Lines 34-37: Use inclusion-exclusion.
• Space: O(m*n)—BIT array.

This is like a 2D sum ninja!

Alternative Solution: 2D Segment Tree

Why an Alternative Approach?

The 2D Segment Tree offers a structured alternative—O(log m * log n) for updates and queries, O(m*n) space. It’s more intuitive, using a tree of trees to represent ranges, but takes more space than BIT. It’s like a detailed 2D map—great for understanding the concept!

How It Works

Imagine a tree for rows, each node holding a tree for columns:

• Step 1: Build:
• Root sums entire matrix; children split rows, then columns.
• Step 2: Update:
• Update leaf, propagate up row and column trees.
• Step 3: Query:
• Combine sums of nodes covering the region.
• Step 4: Why It Works:
• Logarithmic access via tree structure.

Step-by-Step Example

Example: matrix = [[1, 2], [3, 4]]

• Build: Tree represents sums hierarchically.
• SumRegion(0, 0, 1, 1):
• Root sum = 10.
• Update(0, 0, 5):
• Adjust leaf, update ancestors, new sum = 14.

Code for 2D Segment Tree Approach

Copy codeclass NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        self.m, self.n = len(matrix), len(matrix[0])
        self.matrix = matrix
        self.tree = [[0] * (2 * self.n) for _ in range(2 * self.m)]
        # Build row trees
        for i in range(self.m):
            for j in range(self.n, 2 * self.n):
                self.tree[i + self.m][j] = matrix[i][j - self.n]
            for j in range(self.n - 1, 0, -1):
                self.tree[i + self.m][j] = self.tree[i + self.m][2*j] + self.tree[i + self.m][2*j+1]
        # Build column trees
        for j in range(2 * self.n):
            for i in range(self.m - 1, 0, -1):
                self.tree[i][j] = self.tree[2*i][j] + self.tree[2*i+1][j]

    def update(self, row: int, col: int, val: int) -> None:
        diff = val - self.matrix[row][col]
        self.matrix[row][col] = val
        r, c = row + self.m, col + self.n
        self.tree[r][c] = val
        # Update column tree
        while c > 1:
            left = c if c % 2 == 0 else c - 1
            right = c if c % 2 == 1 else c + 1
            self.tree[r][c // 2] = self.tree[r][left] + self.tree[r][right]
            c //= 2
        # Update row tree
        while r > 1:
            left = r if r % 2 == 0 else r - 1
            right = r if r % 2 == 1 else r + 1
            for j in range(2 * self.n):
                self.tree[r // 2][j] = self.tree[left][j] + self.tree[right][j]
            r //= 2

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        def get_row_sum(r, c1, c2):
            sum = 0
            l, r = c1 + self.n, c2 + self.n
            while l <= r:
                if l % 2 == 1:
                    sum += self.tree[r][l]
                    l += 1
                if r % 2 == 0:
                    sum += self.tree[r][r]
                    r -= 1
                l //= 2
                r //= 2
            return sum

        sum = 0
        r1, r2 = row1 + self.m, row2 + self.m
        while r1 <= r2:
            if r1 % 2 == 1:
                sum += get_row_sum(r1, col1, col2)
                r1 += 1
            if r2 % 2 == 0:
                sum += get_row_sum(r2, col1, col2)
                r2 -= 1
            r1 //= 2
            r2 //= 2
        return sum

• Time: O(m*n) build, O(log m * log n) update/query.
• Space: O(m*n)—tree array.

It’s a detailed 2D sum explorer!

Comparing the Two Solutions

• 2D BIT (Best):
• Pros: O(log m * log n) update/query, compact.
• Cons: Less intuitive.
• 2D Segment Tree (Alternative):
• Pros: O(log m * log n) update/query, clear structure.
• Cons: More space.

BIT wins for efficiency.

Additional Examples and Edge Cases

• [[1]], update(0,0,2), sum(0,0,0,0): 2.
• [[1,2],[3,4]], sum(0,0,0,1): 3.

Both handle these well.

Complexity Breakdown

• 2D BIT: Build O(m*n), Update/Query O(log m * log n), Space O(m*n).
• 2D Segment Tree: Build O(m*n), Update/Query O(log m * log n), Space O(m*n).

BIT is leaner.

Key Takeaways

• 2D BIT: Clever and fast—bit magic!
• 2D Segment Tree: Structured and visual—robust!
• Python: 2D arrays rock—see [Python Basics](/python/basics).
• 2D Ranges: Dynamic grids are exciting.

Final Thoughts: Conquer 2D Sums

LeetCode 308: Range Sum Query 2D - Mutable in Python is a thrilling 2D challenge. The 2D BIT offers speed and elegance, while the Segment Tree provides clarity. Want more? Try LeetCode 307: Range Sum Query - Mutable or LeetCode 304: Range Sum Query 2D - Immutable. Ready to sum? Head to Solve LeetCode 308 on LeetCode and tackle those regions today!