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 module init function 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 along with the struct object. Here is an example of the consecutive inputs to the sum_region() function:

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

# Example - 1
numMatrix.sum_region(%NumMatrix{}, 0, 0, 2, 2)

# Example - 2
numMatrix.sum_region(%NumMatrix{}, 0, 1, 3, 2)

# Example - 3
numMatrix.sum_region(%NumMatrix{}, 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 module, whose skeleton is provided in the code playground below. You will need to implement the following methods:

• init(matrix): This function initializes the struct object with the integer matrix, matrix.

• sum_region(obj, row1, col1, row2, col2): 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)$.