Back to solutions

Range Sum Query 2D Immutable

MediumArrays

Answer rectangle-sum queries on a fixed matrix in O(1).

Open problem
Constraints
  • 1 <= rows, cols <= 200
  • 1 <= q <= 10^4

2D prefix sums

Time O(rows*cols) build, O(1) querySpace O(rows*cols)

Precompute pre[i][j] = sum of the rectangle from (0,0) to (i-1,j-1). Any sub-rectangle sum is found by inclusion-exclusion: pre[r2+1][c2+1] - pre[r1][c2+1] - pre[r2+1][c1] + pre[r1][c1]. Building the table is O(rows*cols) and each query is O(1).

Key terms
2D prefix sum:
A table where each cell stores the sum of everything above-and-left of it.
inclusion-exclusion:
Combining four corner prefix sums to isolate a sub-rectangle.
long long sumRegion(int r1, int c1, int r2, int c2) {
    return pre[r2+1][c2+1] - pre[r1][c2+1] - pre[r2+1][c1] + pre[r1][c1];
}
Step by step
  1. Build pre with an extra zero row and column; pre[i+1][j+1] = m[i][j] + top + left - topLeft.
  2. For a query, take the bottom-right prefix and subtract the top and left strips.
  3. Add back the doubly-subtracted top-left corner.
  4. Return the result in O(1).