Lazy Propagation

Lazy propagation is a segment tree technique that delays range updates until the affected child nodes are actually needed.

It keeps range updates efficient by storing pending work.

Core Idea

If an update covers a whole segment, the algorithm updates that segment’s stored answer and records a lazy value instead of immediately updating every child.

When a later query or update needs the children, the pending lazy value is pushed down.

Python Example

def apply(node, left, right, delta, tree, lazy):
    tree[node] += delta * (right - left + 1)
    lazy[node] += delta

For a range-sum segment tree, adding delta to every element in a segment increases the stored sum by delta * segment_length.

Common Confusions

Lazy propagation is not a separate data structure. It is an extension of a segment tree.

The lazy value must mean exactly the pending update for that node. Range assignment, range addition, and other updates need different lazy rules.

When To Use It

Use lazy propagation when both range updates and range queries are frequent and updating each element directly would be too slow.