DSA problem
Range Sum Query 2D - Immutable
Given a 2D matrix matrix, handle multiple queries of the following type:
Calculate the sum of the elements of matrix inside the rectangle defined by its upper-left corner (row1, col1) and lower-right corner (row2, col2).
Implement the NumMatrix class:
NumMatrix(int[][] matrix)initializes the object with the integer matrixmatrix.int sumRegion(int row1, int col1, int row2, int col2)returns the sum of the elements ofmatrixinside the rectangle defined by its upper-left corner(row1, col1)and lower-right corner(row2, col2).
You must design an algorithm where sumRegion works on O(1) time complexity. The idea is to precompute a 2D prefix-sum table during construction, where prefix[i][j] holds the sum of all elements in the sub-rectangle from (0,0) to (i-1,j-1). Any rectangle sum is then recovered by inclusion-exclusion using four table lookups.
Examples
Example 1
Input:
["NumMatrix","sumRegion","sumRegion","sumRegion"]
[[[[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]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]Output:
[null, 8, 11, 12]Explanation: After NumMatrix is built from the 5x5 matrix: sumRegion(2,1,4,3) sums the rectangle from (2,1) to (4,3) = 8; sumRegion(1,1,2,2) = 11; sumRegion(1,2,2,4) = 12.
Constraints
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 200
- -10^4 <= matrix[i][j] <= 10^4
- 0 <= row1 <= row2 < m
- 0 <= col1 <= col2 < n
- At most 10^4 calls will be made to sumRegion.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.