Lazy Propagation
Range updates are stored on nodes and pushed to children only when needed.
Decision · step 2 of 15Segment Tree: Add to a range and leave the tags pending
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.
What you will see
A pending update badge sits on a node until a query or update descends through it.
Cost
| Best | O(log n) |
|---|---|
| Average | O(log n) |
| Worst | O(log n) |
| Space | O(n) |
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
Segment Tree covers these too, in the same run.