2013. Rectangle Totals While Cells Change
A grid of R rows and C columns starts at zero, numbered from 1. Then q
operations arrive:
add r c v add v to the cell at row r, column c
sum r1 c1 r2 c2 print the total of every cell in that rectangle, corners included
add 1 1 5
sum 1 1 1 1 -> 5
add 2 2 3
sum 1 1 2 2 -> 8
sum 2 2 3 3 -> 3
## What most people try first
A 2D prefix-sum table, which answers any rectangle in four lookups. It is the
right tool when the grid never changes, and problem 1536 uses it for exactly
that. Here one add invalidates every prefix below and to the right of the
cell, so rebuilding costs O(R C) per update. At 1000 by 1000 with
2 * 10^5 updates that is 2 * 10^11 operations.
Summing the rectangle directly is the mirror failure: O(R C) per QUERY.
## A Fenwick tree inside a Fenwick tree
Take the one-dimensional tree from problem 2001 and give every node its own tree over the second axis. The update walks the row index upward, and at each stop walks the column index upward:
add(r, c, v): i = r; while i <= R: j = c; while j <= C: t[i][j] += v; j += j&-j
i += i&-i
pre(r, c): sum of t[i][j] over the two downward walks
Both walks strip one bit per step, so a point update touches
log R * log C nodes: at most 100 at the stated limits.
## The rectangle from four prefixes
pre(r, c) gives the total of everything from (1, 1) to (r, c). A rectangle
is then inclusion and exclusion:
sum(r1, c1, r2, c2) = pre(r2, c2) - pre(r1-1, c2) - pre(r2, c1-1) + pre(r1-1, c1-1)
Subtracting the strip above and the strip to the left removes their overlap
twice, so the corner above-left is added back once. The two -1 indices can be
0, and pre of 0 must be 0 rather than an out-of-bounds read, which the
1-indexing gives for free.
## Overflow
10^6 cells of 10^9 total 10^15, far past the 2147483647 a signed 32 bit
integer holds, so the tree entries and the answers need 64 bits. An individual
value of 10^9 fits in 32, and so would 2 * 10^9; it is the accumulation
that does not.
## Cost
O(log R log C) per operation, about 2 * 10^7 node visits across
2 * 10^5 operations, with O(R C) memory.
Constraints - `1 ≤ R, C ≤ 1000` - `1 ≤ q ≤ 200000` - `1 ≤ r ≤ R` and `1 ≤ c ≤ C` - `-10^9 ≤ v ≤ 10^9` - `1 ≤ r1 ≤ r2 ≤ R` and `1 ≤ c1 ≤ c2 ≤ C` - every cell starts at `0`
Input
The first line contains three integers R, C and q.
Each of the next q lines is either add r c v or sum r1 c1 r2 c2.
Output
Print one integer on its own line for every sum operation, in the order the operations arrive: the total of all cells in that rectangle including its corner cells. An add prints nothing.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.