Problem

Given a 2D matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2). And the elements of the matrix could be changed.

You have to implement three functions:

  • NumMatrix(matrix) The constructor.
  • sumRegion(row1, col1, row2, col2) Return the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
  • update(row, col, val) Update the element at (row, col) to val.
  1. The matrix is only modifiable by update.
  2. You may assume the number of calls to update and sumRegion function is distributed evenly.
  3. You may assume that row1 ≤ row2 and col1 ≤ col2.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

Input:
  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]]
  )
  sumRegion(2,1,4,3)
  update(3,2,2)
  sumRegion(2,1,4,3)
Output:
  8
  10

Example 2:

1
2
3
4
5
6

  sumRegion(0, 0, 0, 0)
  update(0, 0, -1)
  sumRegion(0, 0, 0, 0)
Output:
  1
  -1

Solution

Method 1 - Using Fenwick Tree (Binary Indexed Tree)

This problem requires efficiently computing the sum of a sub-rectangle while allowing updates to individual matrix elements. Here’s how we approach the solution:

  • To handle updates efficiently, we’ll use a Fenwick Tree (Binary Indexed Tree) for 2D matrices. Fenwick Trees are ideal for problems requiring modification and querying in logarithmic time.
  • We maintain an auxiliary array that helps compute prefix sums in 2D.
  • The matrix can be updated using the update function, and the sum of a sub-rectangle can be acquired with the sumRegion function using methods derived from prefix sums.

Steps

  1. Constructor (NumMatrix):
    • We initialise the data structures (matrix, tree) and build the Fenwick Tree based on the initial values of the given matrix.
  2. Update Function (update):
    • When an element (row, col) is updated, the difference between the new value and the current value is propagated into the Fenwick Tree.
  3. Sum Region Function (sumRegion):
    • Compute the sum of the rectangle by querying prefix sums from the Fenwick Tree.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

class Solution {
    private int[][] matrix;
    private int[][] tree;
    private int rows, cols;

    public Solution(int[][] matrix) {
        this.rows = matrix.length;
        this.cols = matrix[0].length;
        this.matrix = new int[rows][cols];
        this.tree = new int[rows + 1][cols + 1];

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                update(r, c, matrix[r][c]);
            }
        }
    }

    public void update(int row, int col, int val) {
        int diff = val - matrix[row][col];
        matrix[row][col] = val;
        for (int r = row + 1; r <= rows; r += r & -r) {
            for (int c = col + 1; c <= cols; c += c & -c) {
                tree[r][c] += diff;
            }
        }
    }

    private int sum(int row, int col) {
        int ans = 0;
        for (int r = row + 1; r > 0; r -= r & -r) {
            for (int c = col + 1; c > 0; c -= c & -c) {
                ans += tree[r][c];
            }
        }
        return ans;
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sum(row2, col2) - sum(row2, col1 - 1) - sum(row1 - 1, col2) + sum(row1 - 1, col1 - 1);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution:
    def __init__(self, matrix: List[List[int]]):
        self.rows, self.cols = len(matrix), len(matrix[0])
        self.matrix = [[0] * self.cols for _ in range(self.rows)]
        self.tree = [[0] * (self.cols + 1) for _ in range(self.rows + 1)]

        for r in range(self.rows):
            for c in range(self.cols):
                self.update(r, c, matrix[r][c])

    def update(self, row: int, col: int, val: int) -> None:
        diff = val - self.matrix[row][col]
        self.matrix[row][col] = val
        r = row + 1
        while r <= self.rows:
            c = col + 1
            while c <= self.cols:
                self.tree[r][c] += diff
                c += c & -c
            r += r & -r

    def _sum(self, row: int, col: int) -> int:
        ans = 0
        r = row + 1
        while r > 0:
            c = col + 1
            while c > 0:
                ans += self.tree[r][c]
                c -= c & -c
            r -= r & -r
        return ans

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return (self._sum(row2, col2) 
                - self._sum(row2, col1 - 1) 
                - self._sum(row1 - 1, col2) 
                + self._sum(row1 - 1, col1 - 1))

Complexity

  • ⏰ Time complexity
    • Initialisation (NumMatrix): Building the Fenwick Tree: O(rows * cols * log(rows) * log(cols))
    • Update (update): Updating involves propagating the difference in the Fenwick Tree: O(log(rows) * log(cols)).
    • Query (sumRegion): Fetch prefix sums: O(log(rows) * log(cols)).
  • 🧺 Space complexity: O(rows * cols) for using data structures (tree and matrix): O(rows * cols).