Range Sum Query 2D - Immutable
The key idea
Precompute a 2D prefix-sum table
pre where pre[i][j] is the sum of every cell in the rectangle from (0, 0) to (i-1, j-1). Pad it with a zero top row and left column so the formulas never go out of bounds. Then any rectangle's sum is four table lookups by inclusion-exclusion: big rectangle minus the band above minus the band to the left, plus the corner that was subtracted twice.Problem
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 matrix matrix.
- int sumRegion(int row1, int col1, int row2, int col2) returns the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
You must design an algorithm where sumRegion works in O(1) time complexity.
Constraints
m == matrix.lengthn == matrix[i].length1 <= m, n <= 200-10^4 <= matrix[i][j] <= 10^40 <= row1 <= row2 < m0 <= col1 <= col2 < n- At most
10^4calls will be made tosumRegion.
Examples
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]
Complexity
Time: O(m*n) to build, O(1) per query Space: O(m*n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization