308. Range Sum Query 2D - Mutable

Problem Description

The problem provides a two-dimensional matrix, matrix, and requires us to design a class, NumMatrix, to perform two types of operations efficiently:

1. Update the value at a specific cell (row, col) in the matrix.
2. Calculate the sum of elements within a rectangle specified by its upper left (row1, col1) and lower right (row2, col2) corners.

To encapsulate these operations, the NumMatrix class is required to have the following methods:

• NumMatrix(int[][] matrix) initializes the instance with the matrix.
• void update(int row, int col, int val) updates the value at the matrix cell (row, col) to val.
• int sumRegion(int row1, int col1, int row2, int col2) calculates and returns the sum of the elements within the defined rectangle.

The problem challenges the programmer to find an efficient way to perform both operations considering that there will be multiple queries of both types.

Intuition

A straightforward approach to solve this problem would involve implementing the update function in O(1) time by directly changing the value in the matrix and the sumRegion function in O(R*C) time, where R and C are, respectively, the number of rows and columns to be summed, by iterating through all the numbers in the specified rectangle. However, this naive method would be highly inefficient when dealing with a large matrix and many sumRegion queries.

To improve efficiency, especially for the sum query operation, we can use more sophisticated data structures such as Binary Indexed Trees (BITs) or Segment Trees, which are designed for high-performance range queries. Both of these data structures can help us achieve a better-than-naive time complexity for range sum queries and updates, typically O(logN) for update and query operations.

For this solution, a Binary Indexed Tree (also known as a Fenwick Tree) approach is taken. The concept of a BIT leverages the cumulative frequency up to a given index to compute range sums more efficiently. The BIT is a representation of the matrix that allows both updating an element and querying the prefix sum up to a point in logarithmic time. It uses a clever structure to store cumulative sums with the ability to update frequencies and query cumulative frequencies in O(logN) time complexity.

The solution includes a BinaryIndexedTree class for handling update and query operations on 1D arrays. The NumMatrix class initializes a list of these trees, each representing a row in the matrix, and performs updates and queries using these trees. This allows efficient updates on single elements and fast calculation of rectangle sums by summing the range sums of multiple binary indexed trees corresponding to matrix rows.

Learn more about Segment Tree patterns.

Solution Approach

The solution uses a Binary Indexed Tree (BIT) or Fenwick Tree data structure to optimize both the update and sumRegion operations. A BIT arranges data in such a way that it allows for both update and query operations to be performed in O(logN) time complexity.

Binary Indexed Tree Explained

A Binary Indexed Tree is a data structure that stores cumulative sums of an array and supports two operations efficiently:

• Update: Increments an element in the array and consequently updates the cumulative sums.
• Query: Calculates the prefix sum up to a given index, that is, the sum of all elements from the beginning of the array up to the specified index.

The key idea behind BIT is that it uses a binary representation of indices and exploits the fact that numbers can be decomposed into the sum of powers of 2. This allows for both the update and the query operations to skip over large sections of the array to achieve the desired logarithmic time complexity.

How the BIT is Implemented in the Solution

In the given solution, a BinaryIndexedTree class defines two important functions:

• update(int x, int delta): This function incrementally updates the element at index x by delta and updates all related elements in the BIT. It iteratively adds delta to the current index x and moves to the next index by using the lowbit function, which essentially calculates the length of the interval represented by that index.

  1def update(self, x, delta):
  2    while x <= self.n:
  3        self.c[x] += delta
  4        x += BinaryIndexedTree.lowbit(x)

• query(int x): This function calculates the prefix sum up to index x. It works by iteratively adding the value of the current index to the sum s and moving to the previous relevant index by subtracting the lowbit value from the current index x.

  1def query(self, x):
  2    s = 0
  3    while x > 0:
  4        s += self.c[x]
  5        x -= BinaryIndexedTree.lowbit(x)
  6    return s

Integration with the NumMatrix Class

The NumMatrix class uses the BinaryIndexedTree class to manage each row of the given matrix:

• Initialization (__init__): Here, a list of BinaryIndexedTree instances is created, where each instance corresponds to a row in the matrix. Each element of the row is updated in its corresponding tree during the initialization.

• Updating a cell (update): To update a value in a particular cell identified by (row, col), the difference between the new value and the old value is found by querying the cumulative frequency up until col and the frequency at col-1. This difference val - prev is then used to update the tree for that specific row.

  1def update(self, row: int, col: int, val: int) -> None:
  2    tree = self.trees[row]
  3    prev = tree.query(col + 1) - tree.query(col)
  4    tree.update(col + 1, val - prev)

• Calculating sum of a region (sumRegion): To calculate the sum within a specified region, it iterates through each row from row1 to row2 (inclusive), querying the BinaryIndexedTree for that row for the sum up to col2 and subtracting the sum up to col1-1. Adding these together gives the sum of the rectangle.

  1def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
  2    return sum(
  3        tree.query(col2 + 1) - tree.query(col1)
  4        for tree in self.trees[row1 : row2 + 1]
  5    )

By leveraging BITs, the solution maintains a balance between the time complexity of update and range sum queries, ensuring that both operations are done efficiently even when faced with a large number of queries.

Example Walkthrough

Let's take a small matrix to walk through the example:

1Matrix:
21 2
33 4

We want to initialize the NumMatrix class, perform an update operation, and then perform a sumRegion query to illustrate how the solution approach works.

Step 1: Initializing NumMatrix

1matrix = [
2    [1, 2],
3    [3, 4]
4]
5numMatrix = NumMatrix(matrix)

Upon initialization, a BinaryIndexedTree instance is created for each row in the matrix. The matrix is transformed into a format that the Binary Indexed Trees can work with. This means that after initialization, we have two Binary Indexed Trees corresponding to each row of the matrix.

Step 2: Updating a cell

Let's update the value of the cell at the first row and second column (indexing from 0) to 5. This is how we call the update method:

1numMatrix.update(0, 1, 5)

Now, the matrix and the corresponding Binary Indexed Trees are as follows:

1Matrix:
21 5
33 4
4
5Binary Indexed Trees would internally represent cumulative sums like this:
6Tree for first row: [1, 6]
7Tree for second row: [3, 7]

Step 3: Calculate sum of a region

Suppose we want to calculate the sum of elements within the rectangle from (0, 0) to (1, 1), which covers the entire matrix:

1sum = numMatrix.sumRegion(0, 0, 1, 1)

The query operation would perform as follows:

• The iteration starts from row1, which is 0, and ends at row2, which is 1, inclusive.
• For the first row (row1 or 0), it calculates the sum of the range from the beginning of the row up to col2 (1), which is 6, and subtracts the sum up to col1 - 1 (if col1 is greater than 0), which in this case, isn't subtracted since col1 is 0. This gives us 6 for the first row.
• For the second row (row2 or 1), it does the same operation and calculates the sum across the row up to col2 (1), which is 7, yielding a value of 7.
• The sum of values obtained from all the rows within the specified range is then totaled. In this case, 6 + 7 which equals 13.

The answer is therefore 13, which is indeed the sum of all values in the matrix after the update. By combining these steps, the NumMatrix class can efficiently update values and calculate the sum of regions within the matrix.

Solution Implementation

Time and Space Complexity

Time Complexity

Initialization (NumMatrix.__init__):

• Let m be the number of rows and n be the number of columns in the matrix.
• For each row, we initialize a Binary Indexed Tree (BIT), which takes O(n) time.
• We then update the BIT with each element, taking O(log n) per update.
• This results in O(m * n * log n) time complexity for the initialization of the NumMatrix.

Update (NumMatrix.update):

• Computing the previous value in the BIT involves two query calls, each of which takes O(log n) time.
• Updating the BIT also takes O(log n) time.
• Thus, the update operation has a time complexity of O(log n).

Query (NumMatrix.sumRegion):

• We perform a query operation for each row in the queried region. For row2 - row1 + 1 rows, this results in that many queries.
• Each query involves two calls to BinaryIndexedTree.query, each taking O(log n) time.
• The time complexity for the sumRegion operation is O((row2 - row1 + 1) * log n).

Space Complexity

• Each BIT for a row requires O(n) space.
• With m rows, the space complexity for storing all BITs is O(m * n).
• The input matrix is not modified or copied, and the additional space used for the indices and temporary variables in the methods is O(1).
• Therefore, the space complexity of the NumMatrix class is O(m * n).

Learn more about how to find time and space complexity quickly using problem constraints.