Difference Matrix
Four corner writes per rectangle, then a prefix pass along rows and down columns.
Difference Array: Two overlapping rectangles
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.
Cost
- Best
- O(r * c + q)
- Average
- O(r * c + q)
- Worst
- O(r * c + q)
- Space
- O(r * c)
Before this
Taught by the same lesson
Difference Array covers these too, in the same run.