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).
Intuition
A brute-force sum over the rectangle is O(m * n) per query, and with thousands of queries that multiplies out badly. The trick is the 2D prefix sum — precompute a table where prefix[r][c] holds the sum of all elements from (0,0) to (r-1,c-1). Then any rectangle's sum can be read in O(1) using inclusion-exclusion: add the big rectangle, subtract the two strips you over-counted, add back the corner you subtracted twice. The same idea that turns range-sum queries on a 1D array from O(n) to O(1) works in two dimensions with one extra correction term.
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
Build a 2D prefix-sum table during construction
Create a (m+1) x (n+1) table initialized to zero — the extra row and column of zeros eliminate boundary checks. Fill it with prefix[r+1][c+1] = matrix[r][c] + prefix[r][c+1] + prefix[r+1][c] - prefix[r][c]. Each cell accumulates everything above it, everything to its left, and subtracts the overlap that was double-counted. This runs once in O(m * n).
Answer each query with inclusion-exclusion in O(1)
For the rectangle from (row1, col1) to (row2, col2), the sum is prefix[row2+1][col2+1] - prefix[row1][col2+1] - prefix[row2+1][col1] + prefix[row1][col1]. You subtract the strip above the rectangle and the strip to its left, but that double-subtracts the top-left corner, so you add it back. Drawing the four rectangles on paper makes it obvious why each term is needed.
Why the +1 offset avoids special-casing
Without the padding row and column, queries touching row 0 or column 0 would need if checks because there is no row or column before them to subtract. The padding zeros mean prefix[0][anything] and prefix[anything][0] are zero, so the formula works uniformly. This pattern is standard for prefix sums in any dimension.
Solution
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.