NUHMAN.com

Introduction

LeetCode 308: Range Sum Query 2D - Mutable is an extension of the Range Sum Query - Mutable problem, where instead of a one-dimensional array, you are given a two-dimensional array. The goal is to efficiently handle both updates to individual elements and range sum queries over a submatrix. A brute-force approach would involve recalculating the sum of the elements in the submatrix for each query, but we can use an advanced data structure like a 2D Fenwick Tree (Binary Indexed Tree, BIT) to efficiently update elements and calculate the sum of any submatrix.

Problem Statement

Given a 2D matrix matrix of integers, implement a data structure that supports the following two operations:

• update(row, col, val): Update the element at position (row, col) to val.
• sumRegion(row1, col1, row2, col2): Return the sum of the elements of the submatrix from (row1, col1) to (row2, col2) (inclusive).

Both operations should be handled efficiently.

Example

python

# Example 1
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, 3, 2], [0, 0, 1, 1]]
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); // returns 8 (sum of the submatrix from (2,1) to (4,3) = 8)
    numMatrix.update(3, 3, 2);       // matrix[3][3] = 2
    numMatrix.sumRegion(0, 0, 2, 4); // returns 10 (sum of the submatrix from (0,0) to (2,4) = 10)

Step-by-Step Solution

🧠 Intuition

This problem involves two operations on a 2D array:

1. Range Sum Queries: Efficiently calculate the sum of elements in a submatrix (from (row1, col1) to (row2, col2)).
2. Updates: Modify the value at a specific position and adjust the data structure to reflect this change.

A brute-force approach that recalculates the sum for each query would be inefficient. Instead, we can use a 2D Fenwick Tree (BIT), which is a data structure that efficiently supports both point updates and range sum queries.

✅ Approach

1. 2D Fenwick Tree (Binary Indexed Tree):

• The Fenwick Tree is extended to handle 2D range sums.
• The idea is to maintain a tree structure where each element stores the sum of a specific region of the matrix. Using this structure, both updates and sum queries can be processed in O(log n * log m) time, where n is the number of rows and m is the number of columns in the matrix.

1. Operations:

• update(row, col, val): To update the value at (row, col), calculate the difference between the new value (val) and the old value, and propagate this difference through the 2D Fenwick Tree.
• sumRegion(row1, col1, row2, col2): To compute the sum of the submatrix from (row1, col1) to (row2, col2), we query the Fenwick Tree for the sums of four regions and combine them to get the required sum.

1. 2D Fenwick Tree Structure:

• The 2D Fenwick Tree stores cumulative sums over rectangular regions of the matrix.
• The update operation modifies values at a specific location and propagates the change through the tree.
• The sum operation queries the tree to find the sum of values within a rectangular region.

✅ Python Code

python

class NumMatrix:

    def __init__(self, matrix: list[list[int]]):
        if not matrix or not matrix[0]:
            return
        
        self.m, self.n = len(matrix), len(matrix[0])
        self.bit = [[0] * (self.n + 1) for _ in range(self.m + 1)]
        
        # Initialize Fenwick Tree (BIT)
        for i in range(self.m):
            for j in range(self.n):
                self.update(i, j, matrix[i][j])

    def update(self, row: int, col: int, val: int) -> None:
        # Update the BIT at (row, col) with new value val
        diff = val - self.sumRegion(row, col, row, col)
        row += 1
        col += 1
        while row <= self.m:
            temp_col = col
            while temp_col <= self.n:
                self.bit[row][temp_col] += diff
                temp_col += temp_col & -temp_col
            row += row & -row

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        # Return the sum of the region (row1, col1) to (row2, col2)
        return (self.query(row2, col2) - self.query(row1 - 1, col2) 
                - self.query(row2, col1 - 1) + self.query(row1 - 1, col1 - 1))

    def query(self, row: int, col: int) -> int:
        # Get the sum of the region (1, 1) to (row, col)
        row += 1
        col += 1
        total = 0
        while row > 0:
            temp_col = col
            while temp_col > 0:
                total += self.bit[row][temp_col]
                temp_col -= temp_col & -temp_col
            row -= row & -row
        return total

🧪 How It Works

1. Constructor (__init__):

• The constructor initializes the matrix and creates the 2D Fenwick Tree (bit) to manage the range sums.
• It initializes the Fenwick Tree by iterating over the matrix and updating the tree with each element using the update method.

1. update(row, col, val):

• The update method calculates the difference between the new value (val) and the current value at position (row, col).
• This difference is then propagated through the 2D Fenwick Tree by adjusting the relevant entries in the tree.

1. sumRegion(row1, col1, row2, col2):

• To compute the sum of a submatrix from (row1, col1) to (row2, col2), the method queries the Fenwick Tree for four rectangular sums and combines them to get the desired result.

1. query(row, col):

• The query method computes the prefix sum of the matrix from (1, 1) to (row, col) using the 2D Fenwick Tree.

⏱️ Time and Space Complexity

MetricValueTime Complexity (update)O(log n * log m)Time Complexity (sumRegion)O(log n * log m)Space ComplexityO(n * m)

• Time Complexity (update): The update operation involves adjusting values in the Fenwick Tree, which takes O(log n * log m) time, where n is the number of rows and m is the number of columns in the matrix.
• Time Complexity (sumRegion): The sum region query is answered in O(log n * log m) time by querying the Fenwick Tree.
• Space Complexity: The space complexity is O(n * m), where n is the number of rows and m is the number of columns in the matrix, as we store the 2D Fenwick Tree.

🔍 Edge Cases

1. Empty Matrix:

• If the matrix is empty, ensure that all operations are handled gracefully, especially during initialization.

1. Multiple Updates to Same Cell:

• If the same cell is updated multiple times, the algorithm should handle this correctly by adjusting the 2D Fenwick Tree.

1. Small Matrices:

• Ensure that queries and updates on small matrices (e.g., 1x1 or 2x2) work without errors.

✅ Conclusion

LeetCode 308: Range Sum Query 2D - Mutable is an extension of the 1D problem to a 2D matrix. Using a 2D Fenwick Tree allows us to efficiently handle both point updates and range sum queries in O(log n * log m) time. This solution provides an efficient way to work with mutable 2D arrays, ensuring that even with many queries and updates, the solution remains performant.