The range update problem
A plain segment tree updates one index at a time. But many problems ask you to add a value to a whole range or set a range to a constant. Touching every leaf would be slow. Lazy propagation fixes this by deferring work.
Lazy tags
Each node gets an extra field, a lazy tag, that records an update owed to its entire segment but not yet applied to its children. When an update fully covers a node's range, we apply it to that node's stored aggregate and stamp the tag, then stop. We do not descend further.
Pushing down
Before we ever recurse into a node's children, whether for a deeper update or a query, we push down its pending tag: apply the tag to both children, merge it into their tags, and clear the parent's tag. This keeps the lazy values consistent exactly where we look.
- Apply: combine the tag into a node's aggregate, accounting for the segment length for sums.
- Compose: when tags stack, combine them in the correct order, which matters for assignment versus addition.
- Push down: move a tag to children just before descending.
Key idea
Store deferred updates as lazy tags and push them to children only when you descend, so range updates and queries both stay logarithmic.