LeetCode Solutions Blog

Range Sum Query 2D - Mutable

Number: 308

Difficulty: Medium

Paid? Yes

Problem Description

Design a data structure that handles two types of operations on a given 2D matrix: (1) updating a cell’s value, and (2) calculating the sum of elements in a submatrix defined by an upper left and a lower right corner.

Key Insights

This is a 2D range sum query problem with updates.
A brute-force approach may be too slow due to frequent updates.
The Binary Indexed Tree (Fenwick Tree) or 2D Segment Tree can support both update and sumRegion queries efficiently.
Use an auxiliary BIT structure to maintain cumulative information to quickly answer sum queries.
Maintain a separate copy of the original matrix to compute differences during updates.

Space and Time Complexity

Time Complexity:

update: O(M*log(M)*log(N)) in worst-case per update, where M and N are the dimensions of the matrix.
sumRegion: O(log(M)*log(N)) per query.

Space Complexity:

O(M*N) for storing the BIT and the matrix.

Solution

We implement a 2D Binary Indexed Tree. When performing an update, compute the difference between the new value and the current value of the cell, and update the BIT accordingly. For sumRegion queries, use the inclusion-exclusion principle on prefix sums from the BIT. This allows both updates and sum queries to be done in logarithmic time relative to the dimensions of the matrix. The BIT is a 2D array where each cell BIT[i][j] contributes to the cumulative sum over a specific range determined by the least significant bit. By iterating properly within the BIT update and query functions, we can ensure that all necessary BIT cells are updated or summed.

Code Solutions

class NumMatrix:
    def __init__(self, matrix):
        # initialize dimensions and store given matrix copy
        if not matrix or not matrix[0]:
            return
        self.m = len(matrix)
        self.n = len(matrix[0])
        self.matrix = [[0] * self.n for _ in range(self.m)]
        # BIT is 1-indexed so allocate with extra row and col
        self.bit = [[0] * (self.n + 1) for _ in range(self.m + 1)]
        # Initialize BIT with the matrix values
        for i in range(self.m):
            for j in range(self.n):
                self.update(i, j, matrix[i][j])
                
    def update(self, row, col, val):
        # find the difference from the current value
        if self.m == 0 or self.n == 0: 
            return
        diff = val - self.matrix[row][col]
        self.matrix[row][col] = val
        # update BIT for all indexes that include cell (row, col)
        i = row + 1
        while i <= self.m:
            j = col + 1
            while j <= self.n:
                self.bit[i][j] += diff
                # j moves to next index responsible for including col
                j += (j & -j)
            i += (i & -i)

    def _bitSum(self, row, col):
        # Compute prefix sum from BIT for submatrix (0,0) to (row, col)
        s = 0
        i = row
        while i > 0:
            j = col
            while j > 0:
                s += self.bit[i][j]
                j -= (j & -j)
            i -= (i & -i)
        return s

    def sumRegion(self, row1, col1, row2, col2):
        # Use inclusion-exclusion principle to get region sum
        sum_total = self._bitSum(row2 + 1, col2 + 1)
        sum_top = self._bitSum(row1, col2 + 1)
        sum_left = self._bitSum(row2 + 1, col1)
        sum_corner = self._bitSum(row1, col1)
        return sum_total - sum_top - sum_left + sum_corner