729. Rectangle Totals in Constant Time
An R by C grid is given, then q queries. Each query is r1 c1 r2 c2 and asks for the
total of the rectangle with top-left corner (r1, c1) and bottom-right corner (r2, c2),
inclusive. Rows and columns are numbered from 1.
Print one total per query.
``` grid 1 2 3 4 5 6 7 8 9
(1 1 3 3) -> 45 (2 2 2 2) -> 5 (2 1 3 2) -> 24 ```
## The table of corner totals
Build P, where P[r][c] is the total of the whole rectangle from (1,1) to (r,c). It is
filled in one pass, each cell from its three neighbours:
P[r][c] = grid[r][c] + P[r-1][c] + P[r][c-1] - P[r-1][c-1]
The subtraction is there because the region above and the region to the left both contain the block above-and-left, so adding them counts it twice.
## Answering a query
total = P[r2][c2] - P[r1-1][c2] - P[r2][c1-1] + P[r1-1][c1-1]
Start with everything up to the bottom-right corner, remove the strip above, remove the strip to the left, then ADD BACK the corner block that both removals took away.
That final + is inclusion-exclusion, and leaving it out is the single most common error with
this structure. It is invisible on any query touching the top or left edge, because the term is
then zero, so it only shows on a rectangle strictly inside the grid. The query (2 2 2 2) is
the smallest case that catches it.
## The row and column of zeros
Size P as (R+1) by (C+1) and leave row 0 and column 0 as zeros. Then r1-1 and c1-1
are always valid indices and no query needs a bounds check.
Sizing it R by C and guarding every access with an if works too, and it is four extra
branches in the hot path for nothing.
## This is problem 61 in two dimensions
61 answers range queries on a line with one prefix array and one subtraction. Here it is one
table and three. The pattern generalises to any number of dimensions, with 2^k terms in the
query.
## Overflow
A 1000 by 1000 grid is 10^6 cells of magnitude up to 10^9, so the corner table reaches
10^15 and every query answer is bounded by the same figure. Both need 64 bits.
## What most people try first
Answering each query by walking its rectangle. A single query can cover the whole grid, so with
2 * 10^5 queries over a 1000 by 1000 grid that is 2 * 10^11 cell reads. The
table is built once and every query after it costs four lookups.
## Cost
Time O(R C + q). Space O(R C).
Constraints - `1 ≤ R, C ≤ 1000` - `1 ≤ q ≤ 200000` - `-10^9 ≤ each value ≤ 10^9` - `1 ≤ r1 ≤ r2 ≤ R` - `1 ≤ c1 ≤ c2 ≤ C`
Input
The first line contains three integers R, C and q.
The next R lines contain C integers each.
Each of the next q lines contains four integers r1, c1, r2, c2.
Output
Print q lines, one total per query.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.