Range Sum Query 2D - Immutable
Range Sum Query 2D - Immutable: given a 2D matrix matrix, handle multiple queries asking for the sum of elements inside a rectangle defined by its upper-left corner (row1, col1) and lower-right corner (row2, col2).
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 200
- -10⁴ <= matrix[i][j] <= 10⁴
- 0 <= row1 <= row2 < m
- 0 <= col1 <= col2 < n
- At most 10⁴ calls will be made to sumRegion.
Intuition
Range sum query 2d immutable answers repeated rectangle-sum queries on a fixed matrix. Summing each rectangle directly is O(mn) per query, which fails when queries are many — and the word immutable is the hint that preprocessing is the intended trade.
Since the matrix never changes, work done once can serve every query:
- Build a 2D prefix-sum table where prefix[i][j] holds the sum of the rectangle from the origin to (i, j), then answer any query in O(1).
The table is built with inclusion-exclusion. Each cell is its own value plus the rectangle above plus the rectangle to the left, minus the overlap counted twice: prefix[i][j] = matrix[i][j] + prefix[i-1][j] + prefix[i][j-1] − prefix[i-1][j-1].
Queries reverse the same idea. The sum of a rectangle from (r1, c1) to (r2, c2) is the big rectangle minus the strip above, minus the strip to the left, plus the top-left corner added back — because subtracting both strips removed that corner twice.
Forgetting to add the corner back is the defining bug of this problem, and it produces answers that are too small in a way that only shows on rectangles not touching the origin.
Using a table with one extra row and column of zeros removes every boundary check. Queries touching row 0 or column 0 then index into the padding rather than needing an if.
Preprocessing is O(mn) once, each query is O(1), and space is O(mn) for the table.
Whenever a problem gives you a fixed grid and asks for repeated rectangle-sum queries, the shape is a 2D prefix sum. The tell is: the data does not change, but you need aggregate information over many sub-rectangles. The 1D version (subarray sums) and this 2D version are the same inclusion-exclusion idea, just with one more correction term per added dimension.
Approach
Before reading on: price up what the direct approach costs here, then ask what running total makes each query a single subtraction. Aim for O(m * n) construction, O(1) per query time and O(m * n) space.
Trade preprocessing for query speed
The matrix never changes, so work done once serves every query. That is what the word immutable in the title is signalling.
Define the prefix table
prefix[i][j] is the sum of the whole rectangle from the origin to (i, j). Every query is then a combination of four such values.
Build with inclusion-exclusion
prefix[i][j] = matrix[i][j] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]. The overlap is subtracted because it was counted twice.
Pad with a zero row and column
An extra row and column of zeros removes every boundary check — queries touching row 0 index into the padding instead of needing a conditional.
Answer queries in four lookups
Take the big rectangle, subtract the strip above and the strip to the left, then add the top-left corner back — subtracting both strips removed it twice.
Watch the corner term
Omitting the added-back corner is the defining bug, producing answers that are too small only for rectangles not touching the origin.
Cost of the structure
Preprocessing is O(m · n) once, each query is O(1), and space is O(m · n) for the table.
Solution & live demo
Common pitfalls
Forgetting to add back the double-subtracted corner
return self.prefix[row2+1][col2+1] - self.prefix[row1][col2+1] - self.prefix[row2+1][col1]
return self.prefix[row2+1][col2+1] - self.prefix[row1][col2+1] - self.prefix[row2+1][col1] + self.prefix[row1][col1]
The top strip and left strip overlap in the top-left corner. Subtracting both removes that corner twice, so you must add prefix[row1][col1] back. Without it, queries whose rectangle does not touch row 0 or column 0 return values that are too small.
Building the prefix table without the padding row/column
self.prefix = [[0] * n for _ in range(m)]
self.prefix = [[0] * (n + 1) for _ in range(m + 1)]
Without padding, the construction formula tries to read prefix[r-1][c] when r == 0, hitting an index error or requiring an if guard on every cell. The extra row and column of zeros make the recurrence work uniformly.
Swapping row and column indices in the query
return self.prefix[col2+1][row2+1] - self.prefix[col1][row2+1] - self.prefix[col2+1][row1] + self.prefix[col1][row1]
return self.prefix[row2+1][col2+1] - self.prefix[row1][col2+1] - self.prefix[row2+1][col1] + self.prefix[row1][col1]
The prefix table is indexed [row][col]. Transposing the indices reads from the wrong position, returning garbage for any non-square matrix.
Edge cases
The formula reduces to prefix[m][n] - 0 - 0 + 0, which is the total sum. No special branch needed.
(r, c) to (r, c)The inclusion-exclusion still works: it computes prefix[r+1][c+1] - prefix[r][c+1] - prefix[r+1][c] + prefix[r][c], which collapses to matrix[r][c].
Prefix sums are pure addition — negatives flow through correctly. No abs or clamping is needed.