AlgoScope

Difference Matrix

Four corner writes per rectangle, then a prefix pass along rows and down columns.

Range queries, algorithm, advanced
Rectangle 1: four corner writes.012345stop0123stop0500-500000000000000000-5005000000000
Rectangle 1: four corner writes.012345stop0123stop0500-500000000000000000-5005000000000

Difference Array: Two overlapping rectangles

Decision, step 2 of 16

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.

How difference array works

Cost

Best
O(r * c + q)
Average
O(r * c + q)
Worst
O(r * c + q)
Space
O(r * c)

Taught by the same lesson

Difference Array covers these too, in the same run.