Difference Matrix
Four corner writes per rectangle, then a prefix pass along rows and down columns.
Rectangle rows 0 to 2, columns 1 to 3, +5. Four writes: +5 at (0,1) starts it; -5 at (0,4) stops it past the right edge; -5 at (3,1) stops it below the bottom; +5 at (3,4) cancels the corner that both stops would hit.
What you will see
Four corners receive plus and minus marks; the prefix pass reveals the final grid.
Cost
| Best | O(r * c + q) |
|---|---|
| Average | O(r * c + q) |
| Worst | O(r * c + q) |
| Space | O(r * c) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, try operations in any order.
Screen readers: Structure nodes announce the range they cover and their value; each step announces which nodes answer the query.
Reduced motion: Contributing nodes highlight statically; no path animation.
Before this
Taught by the same lesson
Difference Array covers these too, in the same run.