AlgoScope

Lazy Propagation

Range updates are stored on nodes and pushed to children only when needed.

Range queries, algorithm, advanced
Node covering indices 0 to 7: Straddles: push the tag down and split.58316781364106202108current

Segment Tree: Add to a range and leave the tags pending

Decision, step 2 of 15

This node covers indices 0 to 7. The range covers only part of it, so any tag here is pushed down and both children are visited.

How segment tree works

Cost

Best
O(log n)
Average
O(log n)
Worst
O(log n)
Space
O(n)

Taught by the same lesson

Segment Tree covers these too, in the same run.