304. Range Sum Query 2D - Immutable

Implement a `NumMatrix` class with constructor `NumMatrix(matrix)` and method `sumRegion(row1, col1, row2, col2)` that returns the sum of elements inside the rectangle (inclusive). Use a 2D prefix sum for O(1) queries.

Input Format

Constructor input matrix; queries as parameters.

Output Format

sumRegion returns int.

Constraints

  • m,n ≤ 1000; many sumRegion queries.

Examples

Example 1:

Input:

matrix = [[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]

Output:

8

Explanation:

sumRegion(2,1,4,3) = 8.

Loading...
304. Range Sum Query 2D - Immutable - Matrix