Leetcode 308. Range Sum Query 2D - Mutable
Problem Explanation :
Given a 2D matrix, the goal of this problem is to be able to get the sum of the numbers in a particular rectangle and also the ability to update the numbers in the matrix.
The rectangle is defined by the coordinate of the upper left corner and the coordinate of the lower right corner. The matrix is only modifiable by the update function.
For example, in the matrix provided by the problem,
1 2 3[ 4 [3, 0, 1, 4, 2], 5 [5, 6, 3, 2, 1], 6 [1, 2, 0, 1, 5], 7 [4, 1, 0, 1, 7], 8 [1, 0, 3, 0, 5] 9]
if we take the rectangle defined by (2, 1) the upper left corner and (4, 3) the lower right corner, we would get the following rectangle,
1 2 3[ 4 [2, 0, 1], 5 [1, 0, 1], 6 [0, 3, 0] 7]
the sum of numbers in this rectangle is 8.
Update function receives a coordinate and a new value, it updates the number in the coordinate with the new value.
For example, if update function is called with coordinate (3,2) and value 2, our matrix becomes:
1 2 3[ 4 [3, 0, 1, 4, 2], 5 [5, 6, 3, 2, 1], 6 [1, 2, 0, 1, 5], 7 [4, 1, 2, 1, 7], 8 [1, 0, 3, 0, 5] 9]
After this update, if we re-calculate the sum of same rectangle, now it is 10.
Approach to the Solution:
The solution makes use of a data structure known as a Fenwick Tree (also known as a Binary Indexed Tree).
The FenwickTree is built with the sums of the submatrices that end with each coordinate. Each node of the Fenwick Tree contains the cumulative sums of each of the cells of the matrix, considering the cells from the position cell (1,1) to the current position.
The update operation is made by updating the sums for each cell affected.
The get operation is made by summing the values of the nodes that are part of the sum for the rectangle defined by the parameters.
Fenwick Tree makes update and get operations very efficient, they have a time complexity of O(log^2 n) where n is the number of rows/cols of the matrix.
Java Solution:
1
2java
3class FenwickTree {
4 private final int[][] sums;
5
6 public FenwickTree(int m, int n) {
7 sums = new int[m + 1][n + 1];
8 }
9
10 public void update(int row, int col, int delta) {
11 for (int i = row; i < sums.length; i += i & -i)
12 for (int j = col; j < sums[0].length; j += j & -j)
13 sums[i][j] += delta;
14 }
15
16 public int get(int row, int col) {
17 int sum = 0;
18 for (int i = row; i > 0; i -= i & -i)
19 for (int j = col; j > 0; j -= j & -j)
20 sum += sums[i][j];
21 return sum;
22 }
23}
24
25class NumMatrix {
26 private final FenwickTree tree;
27 private final int[][] matrix;
28
29 public NumMatrix(int[][] matrix) {
30 this.matrix = matrix;
31 tree = new FenwickTree(matrix.length, matrix[0].length);
32 for (int i = 0; i < matrix.length; ++i)
33 for (int j = 0; j < matrix[0].length; ++j)
34 tree.update(i + 1, j + 1, matrix[i][j]);
35 }
36
37 public void update(int row, int col, int val) {
38 tree.update(row + 1, col + 1, val - matrix[row][col]);
39 matrix[row][col] = val;
40 }
41
42 public int sumRegion(int row1, int col1, int row2, int col2) {
43 return tree.get(row2 + 1, col2 + 1) - tree.get(row1, col2 + 1) -
44 tree.get(row2 + 1, col1) + tree.get(row1, col1);
45 }
46}
In the Java solution, 'FenwickTree' class implements the Binary Indexed Tree and is used by the 'NumMatrix' class to accomplish the necessary tasks.
'NumMatrix' class calls FenwickTree's update() in its own update(), with correct parameters and updates the sums in the FenwickTree.
In java solution, indexes of arrays are 0 based but in Fenwick tree, they are 1 based (as node at 0 doesn't represent any value in the array). Hence, we do (i+1) and (j+1) while calling FenwickTree's update() function.
In sumRegion(), tree.get(row2 + 1, col2 + 1) - tree.get(row1, col2 + 1) - tree.get(row2 + 1, col1) + tree.get(row1, col1) expression is used to find the sum of values in the specific rectangle.
Python Solution:
1 2python 3class FenwickTree: 4 def __init__(self, m, n): 5 self.sums = [[0]*(n+1) for _ in range(m+1)] 6 7 def update(self, row, col, delta): 8 i = row 9 while i < len(self.sums): 10 j = col 11 while j < len(self.sums[0]): 12 self.sums[i][j] += delta 13 j += j & -j 14 i += i & -i 15 16 def get(self, row, col): 17 sum = 0 18 i = row 19 while i > 0: 20 j = col 21 while j > 0: 22 sum += self.sums[i][j] 23 j -= j & -j 24 i -= i & -i 25 return sum 26 27class NumMatrix: 28 def __init__(self, matrix): 29 self.matrix = matrix 30 self.tree = FenwickTree(len(matrix), len(matrix[0])) 31 for i in range(len(matrix)): 32 for j in range(len(matrix[0])): 33 self.tree.update(i+1, j+1, matrix[i][j]) 34 35 def update(self, row, col, val): 36 self.tree.update(row+1, col+1, val - self.matrix[row][col]) 37 self.matrix[row][col] = val 38 39 def sumRegion(self, row1, col1, row2, col2): 40 return self.tree.get(row2+1, col2+1) - self.tree.get(row1, col2+1) - 41 self.tree.get(row2+1, col1) + self.tree.get(row1, col1)
The Python solution is nearly identical to the Java solution except that Python has dynamic arrays and list comprehension which allows us to create a multidimensional array in a more concise manner. The logic, methods and their purposes remain the same.
JavaScript Solution:
1
2javascript
3class FenwickTree {
4 constructor(m, n) {
5 this.sums = Array.from({length: m + 1}, () => Array(n + 1).fill(0));
6 }
7
8 update(row, col, delta) {
9 for(let i = row; i < this.sums.length; i += i & -i)
10 for(let j = col; j < this.sums[0].length; j += j & -j)
11 this.sums[i][j] += delta;
12 }
13
14 get(row, col) {
15 let sum = 0;
16 for(let i = row; i > 0; i -= i & -i)
17 for(let j = col; j > 0; j -= j & -j)
18 sum += this.sums[i][j];
19 return sum;
20 }
21}
22
23class NumMatrix {
24 constructor(matrix) {
25 if (!matrix.length || !matrix[0].length) return;
26 this.matrix = matrix;
27 this.tree = new FenwickTree(matrix.length, matrix[0].length);
28 for (let i = 0; i < matrix.length; ++i)
29 for (let j = 0; j < matrix[0].length; ++j)
30 this.tree.update(i + 1, j + 1, matrix[i][j]);
31 }
32
33 update(row, col, val) {
34 this.tree.update(row + 1, col + 1, val - this.matrix[row][col]);
35 this.matrix[row][col] = val;
36 }
37
38 sumRegion(row1, col1, row2, col2) {
39 return this.tree.get(row2 + 1, col2 + 1) - this.tree.get(row1, col2 + 1) -
40 this.tree.get(row2 + 1, col1) + this.tree.get(row1, col1);
41 }
42}
Here, the JavaScript solution closely resembles its Java and Python counterparts. The same concepts, methods, and classes are implemented.
C++ Solution:
1
2cpp
3class FenwickTree {
4 vector<vector<int>> sums;
5public:
6 FenwickTree(int m, int n) : sums(m + 1, vector<int>(n + 1, 0)) {}
7
8 void update(int row, int col, int delta) {
9 for (int i = row; i < sums.size(); i += i & -i)
10 for (int j = col; j < sums[0].size(); j += j & -j)
11 sums[i][j] += delta;
12 }
13
14 int get(int row, int col) {
15 int sum = 0;
16 for (int i = row; i > 0; i -= i & -i)
17 for (int j = col; j > 0; j -= j & -j)
18 sum += sums[i][j];
19 return sum;
20 }
21};
22
23class NumMatrix {
24private:
25 vector<vector<int>> matrix;
26 FenwickTree tree;
27public:
28 NumMatrix(vector<vector<int>>& matrix): matrix(matrix), tree(matrix.size(), matrix[0].size()) {
29 for (int i = 0; i < matrix.size(); ++i)
30 for (int j = 0; j < matrix[0].size(); ++j)
31 tree.update(i + 1, j + 1, matrix[i][j]);
32 }
33
34 void update(int row, int col, int val) {
35 tree.update(row + 1, col + 1, val - matrix[row][col]);
36 matrix[row][col] = val;
37 }
38
39 int sumRegion(int row1, int col1, int row2, int col2) {
40 return tree.get(row2 + 1, col2 + 1) - tree.get(row1, col2 + 1) -
41 tree.get(row2 + 1, col1) + tree.get(row1, col1);
42 }
43};
The C++ solution again follows the same logic and approach as solutions in Java and Python. Classes, methods and operations in these classes are similar, just a different syntax being C++.
C# Solution:
1
2csharp
3public class FenwickTree {
4 private int[][] sums;
5
6 public FenwickTree(int m, int n) {
7 sums = new int[m + 1][];
8 for (int i = 0; i < m + 1; i++)
9 sums[i] = new int[n + 1];
10 }
11
12 public void Update(int row, int col, int delta) {
13 for (int i = row; i < sums.Length; i += i & -i)
14 for (int j = col; j < sums[0].Length; j += j & -j)
15 sums[i][j] += delta;
16 }
17
18 public int Get(int row, int col) {
19 int sum = 0;
20 for (int i = row; i > 0; i -= i & -i)
21 for (int j = col; j > 0; j -= j & -j)
22 sum += sums[i][j];
23 return sum;
24 }
25}
26
27public class NumMatrix {
28 private FenwickTree tree;
29 private int[][] matrix;
30
31 public NumMatrix(int[][] matrix) {
32 this.matrix = matrix;
33 tree = new FenwickTree(matrix.Length, matrix[0].Length);
34 for (int i = 0; i < matrix.Length; ++i)
35 for (int j = 0; j < matrix[0].Length; ++j)
36 tree.Update(i + 1, j + 1, matrix[i][j]);
37 }
38
39 public void Update(int row, int col, int val) {
40 tree.Update(row + 1, col + 1, val - matrix[row][col]);
41 matrix[row][col] = val;
42 }
43
44 public int SumRegion(int row1, int col1, int row2, int col2) {
45 return tree.Get(row2 + 1, col2 + 1) - tree.Get(row1, col2 + 1) -
46 tree.Get(row2 + 1, col1) + tree.Get(row1, col1);
47 }
48}
In addition to classes FenwickTree and NumMatrix being named starting with Capital letters, getters and methods are also named starting with a Capital letter as per C# language syntax rules. Except these naming differences, the code to calculate sum and update value in a matrix using Fenwick tree is the same as other languages.## Swift Solution:
1
2swift
3class FenwickTree {
4 var sums: [[Int]]
5
6 init(_ m: Int, _ n: Int) {
7 sums = Array(repeating: Array(repeating: 0, count: n+1), count: m+1)
8 }
9
10 func update(row: Int, col: Int, delta: Int) {
11 var i = row
12 while i < sums.count {
13 var j = col
14 while j < sums[0].count {
15 sums[i][j] += delta
16 j += j & -j
17 }
18 i += i & -i
19 }
20 }
21
22 func get(row: Int, col: Int) -> Int {
23 var sum = 0
24 var i = row
25 while i > 0 {
26 var j = col
27 while j > 0 {
28 sum += sums[i][j]
29 j -= j & -j
30 }
31 i -= i & -i
32 }
33 return sum
34 }
35}
36
37class NumMatrix {
38
39 var tree: FenwickTree
40 var matrix: [[Int]]
41
42 init(_ matrix: [[Int]]) {
43 self.matrix = matrix
44 tree = FenwickTree(matrix.count, matrix[0].count)
45 for i in 0 ..< matrix.count {
46 for j in 0 ..< matrix[0].count {
47 tree.update(row: i + 1, col: j + 1, delta: matrix[i][j])
48 }
49 }
50 }
51
52 func update(_ row: Int, _ col: Int, _ val: Int) {
53 tree.update(row: row + 1, col: col + 1, delta: val - matrix[row][col])
54 matrix[row][col] = val
55 }
56
57 func sumRegion(_ row1: Int, _ col1: Int, _ row2: Int, _ col2: Int) -> Int {
58 return tree.get(row: row2 + 1, col: col2 + 1) - tree.get(row: row1, col: col2 + 1) -
59 tree.get(row: row2 + 1, col: col1) + tree.get(row: row1, col: col1)
60 }
61}
In the Swift solution, we first defined class FenwickTree and its operations. A new matrix with additional row and column filled with zero is maintained to store the cumulative sum. In update() function, delta is added to each relevant cell of the sums matrix.
In the NumMatrix class, the tree object is created with the number of rows and columns of the matrix. The existing values of the matrix are added to the tree. When an update is required, the change is calculated and passed to the FenwickTree object's update function.
The sumRegion function calculates the sum of the rectangle defined by the top left coordinate (row1, col1) and the bottom right (row2, col2). It calls the FenwickTree get function to retrieve the cumulative sum up to the required rows and columns and performs calculations to get the sum of the defined region.
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.