Range Sum Query 2D — Immutable
Given an integer matrix that never changes, preprocess it so that many queries of the form "sum of the rectangle with corners (r1, c1) and (r2, c2)" can each be answered in constant time.
- 1 ≤ m, n ≤ 200
- -10^4 ≤ matrix[i][j] ≤ 10^4
- Up to 10^4 queries
- Immutable data, many range queries
- Rectangle sums decompose by inclusion–exclusion
- 2D prefix table with a padding row and column
If many queries ask for an aggregate over [l, r] and the aggregate has an inverse (sum, XOR, product without zeros), precompute P[i] = agg(a[0..i)) once so every query becomes P[r+1] - P[l]. Combined with a hash map of seen prefix values it counts subarrays with a given sum in one pass; the inverse trick (difference array) makes range updates O(1).
Build P[i][j] = sum of the sub-matrix from (0,0) to (i-1, j-1) using P[i][j] = a[i-1][j-1] + P[i-1][j] + P[i][j-1] - P[i-1][j-1]. A rectangle sum is then P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1], subtracting the two overlapping strips and adding back their doubly subtracted corner.
- Per-row prefix sums give O(m) per query with the same memory. If updates are needed, a 2D Fenwick tree offers O(log m · log n) for both operations.