Algorithms / Segment Tree Lazy Propagation

Least You Need to Know: Lazy Propagation for Range Updates and Range Queries

Lazy propagation lets a segment tree postpone pushing range updates into children until that detail is actually needed. The main idea is to keep a pending tag that says, in effect, 'this whole interval has already been updated even if the children are not individually refreshed yet.'

The least you need to know

Lazy propagation stores deferred update information at internal nodes.
A lazy tag means the node value already reflects an update, even if children have not been individually adjusted yet.
Before descending to children, pending lazy information is usually pushed downward.
Lazy propagation is useful when both updates and queries affect ranges, not just single points.
Segment trees often use about `4n` array space in interview implementations.

Key notation

lazy[node] pending update still to be propagated to children

push transfer a pending tag to child nodes before deeper recursion

4n common safe array size for tree storage in interviews

Tiny worked example

Suppose you add 5 to every element in a query range.
If a node interval is fully covered, increase its stored aggregate and record a lazy tag instead of updating every descendant immediately.
Later, if a partial-overlap query needs the children, push that tag down first.
This deferral keeps both range updates and queries efficient.

Common mistakes

Students sometimes forget to update the node's own aggregate when attaching a lazy tag.
Pushing lazy tags too late or never can make child answers stale.
Lazy propagation is for deferred range effects, not for unrelated balancing.

How to recognize this kind of problem

The problem needs many range updates plus many range queries.
Point-update structures are no longer sufficient.
You want to defer work on untouched subtrees until a later query or deeper update needs it.