The motivation
A plain segment tree updates one element at a time. To add a value to a whole range, touching every covered leaf would be slow. Lazy propagation lets a segment tree apply a range update in the same fast time as a range query.
Pending tags
When a range update covers a node entirely, do not push it down to the children. Instead:
- Apply the update to that node's stored aggregate immediately.
- Record a pending tag on the node describing the deferred work for its subtree.
The children stay untouched and possibly stale, which is fine because nobody has looked at them yet.
Push down on demand
Later, when a query or update must enter a node's children, you first push down the pending tag: apply it to both children's aggregates, copy the tag onto them, and clear it on the parent. The laziness pays off because most pending work never needs to be pushed all the way to the leaves.
This keeps both range updates and range queries efficient, and it composes for operations like range add with range sum, or range assign with range maximum, as long as tags combine cleanly.
Key idea
Tag a fully covered node with deferred work and only push that tag to its children when a later operation must descend past it.