Range Sum Query 2D - Immutable
Medium · Matrix · Array · Design · Matrix · Prefix Sum
Problem
Design a class that answers many rectangle-sum queries on a fixed 2D integer matrix.
- NumMatrix(matrix) stores the m x n matrix.
- sumRegion(row1, col1, row2, col2) returns the sum of every cell in the rectangle whose upper-left corner is (row1, col1) and lower-right corner is (row2, col2), both inclusive.
The matrix never changes after construction. Each sumRegion call should run in O(1) time.
The input is the list of operations and the list of their arguments, and the output lists what each call returns (null for the constructor).
Examples
Input: ops = ["NumMatrix","sumRegion","sumRegion","sumRegion"], args = [[[[2,0,1],[4,3,5],[1,6,2]]],[0,0,1,1],[1,1,2,2],[2,0,2,2]] Output: [None, 9, 16, 9]
The queries cover 2 + 0 + 4 + 3, then 3 + 5 + 6 + 2, then the bottom row 1 + 6 + 2.
Input: ops = ["NumMatrix","sumRegion","sumRegion"], args = [[[[-1,4],[7,-2]]],[0,0,1,1],[0,1,1,1]] Output: [None, 8, 2]
The whole matrix sums to 8 and the right column to 2.
Input: ops = ["NumMatrix","sumRegion","sumRegion"], args = [[[[1,2,3],[4,5,6]]],[1,2,1,2],[0,0,0,0]] Output: [None, 6, 1]
A rectangle whose corners coincide is one cell: 6, then 1.
Constraints
- 1 <= m, n <= 200
- -10^4 <= matrix[i][j] <= 10^4
- 0 <= row1 <= row2 < m
- 0 <= col1 <= col2 < n
- At most 10^4 calls are made to sumRegion
Approaches
- Prefix sums per row — time O(m · n) to build, O(m) per query, space O(m · n)
Follow-up
What if cells could change between queries? Every update would invalidate O(m · n) prefix entries. A 2D Fenwick (binary indexed) tree supports both updates and rectangle sums in O(log m · log n).
Related problems
Start free on Cariara · Coding problems · System design studio
