Range Sum Query 2D – Immutable

Design a class NumMatrix:

• NumMatrix(matrix) stores a 2D integer grid.
• sum_region(row1, col1, row2, col2) returns the sum of the rectangle with top-left corner (row1, col1) and bottom-right corner (row2, col2), edges included.

The grid never changes; make every sum_region call O(1).

Example 1

matrix =
  [[2, 0,  1, 3],
   [4, 1, -2, 0],
   [1, 5,  2, 1]]

Input:
["NumMatrix", "sum_region", "sum_region",
 "sum_region"]
[[matrix], [0, 0, 1, 1], [1, 1, 2, 3],
 [2, 0, 2, 3]]
Output: [None, 7, 7, 9]

2 + 0 + 4 + 1 = 7; 1 - 2 + 0 + 5 + 2 + 1 = 7; the last row sums to 9.

Example 2

Input:
["NumMatrix", "sum_region"]
[[[[7]]], [0, 0, 0, 0]]
Output: [None, 7]

Example 3

Input:
["NumMatrix", "sum_region", "sum_region"]
[[[[1, 2], [3, 4]]], [0, 0, 1, 1], [0, 1, 1, 1]]
Output: [None, 10, 6]

Constraints

• 1 ≤ rows, cols ≤ 300
• -10⁴ ≤ matrix[r][c] ≤ 10⁴
• 0 ≤ row1 ≤ row2 < rows, 0 ≤ col1 ≤ col2 < cols
• up to 2 · 10⁴ calls to sum_region