Coding test practice - Undestroyed Buildings
Query: for the rectangular subarray whose top-left is (x1, y1) and bottom-right is(x2, y2),
add the given number x to all of it.
But all queries must be processed in O(NM).
N: length of row
M: length of column
Say there are two queries.
One adds the number x over the range (1, 1) ~ (3, 3).
The other adds the number y over the range (0, 0) ~ (3, 2).
| y | 0 | -y | 0 | 0 |
|---|---|---|---|---|
| 0 | x | 0 | 0 | -x |
| 0 | 0 | 0 | 0 | 0 |
| -y | 0 | y | 0 | 0 |
| 0 | -x | 0 | 0 | x |
Now if you run the following recurrence on the array,
you get the same result as running each of the two queries one by one.