Sign in to watch this lesson
Advanced - Data Structures and Range Queries Ā· 5:24
Lazy Propagation
A range update stops at the O(log n) nodes that cover the range and leaves a note there; a note is handed to both children (a push) only when an update or query has to go below that node, and every parent recomputes its aggregate after its children return. Range add with point reads needs no push at all, range assignment does, and range add with range max or sum combines both, with sums scaling the note by the segment length. Mixed assignment and addition need one composition rule: an assignment wipes a pending addition, and an addition lands on a pending assignment.
You will learn
- Explain why a range update touches only O(log n) covering nodes when changes are left as notes
- Write push(v) and call it before every descent in updates and queries, and recompute parents after the recursive calls
- Implement range add with range max and range sum (scaling notes by the segment length) in O(log n) per operation
- Compose assignment and addition tags with a fixed apply order and test the composition in isolation