DIY: Range Sum Query 2D — Immutable
Solve the interview question "Range Sum Query 2D — Immutable" in this lesson.
We'll cover the following
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 subregion. 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:

__init__(self, matrix)
: This method initializes the object with the integer matrix,matrix
. 
sum_region(self, 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)$.
Level up your interview prep. Join Educative to access 70+ handson prep courses.