DIY: Range Sum Query 2D — Immutable

Problem statement

Given an m * n matrix, you need to handle multiple queries of the following type:

Calculate the sum of the elements of the matrix inside the rectangle defined by its upper left corner, $(row1, col1)$, and lower right corner, $(row2, col2)$.

Constraints

You can assume the following constraints for this problem:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 200
• -105 <= matrix[i][j] <= 105
• 0 <= row1 <= row2 < m
• 0 <= col1 <= col2 < n

Input

The NumMatrix class constructor takes the matrix as the input. The sum_region() function takes the four integer inputs that represent the starting and ending coordinates of the sub-region. Here is an example of the consecutive inputs to the sum_region() function:

numMatrix = NumMatrix(
[
  [1, 3, 5],
  [2, 4, 6],
  [7, 8, 2],
  [9, 3, 6]
])

// Example - 1
numMatrix.sum_region(0, 0, 2, 2)

// Example - 2
numMatrix.sum_region(0, 1, 3, 2)

// Example - 3
numMatrix.sum_region(2, 1, 3, 1)

Output

The output of the sum_region() function is an integer that represents the region’s sum. Here is an example of the output:

// Example - 1
38

// Example - 2
37

// Example - 3
11

Coding exercise

You need to implement the NumMatrix class, whose skeleton is provided in the code playground below. You will need to implement the following methods:

• new(matrix: Vec<Vec<i32>>): This method initializes the object with the integer matrix, matrix.

• sum_region(int row1, int col1, int row2, int col2)-> i32: This method returns the sum of the elements of the matrix inside the rectangle defined by its upper left corner, $(row1, col1)$, and lower right corner, $(row2, col2)$.