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.

Function Contract

apply(node, left, right, delta, tree, lazy) updates one segment-tree node for a range-add operation over a sum tree.

push(node, left, right, tree, lazy) moves a pending range-add update from a parent node to its children before a later operation needs child-level accuracy.

Python Example

def apply(node, left, right, delta, tree, lazy):
    tree[node] += delta * (right - left + 1)
    lazy[node] += delta
 
 
def push(node, left, right, tree, lazy):
    if lazy[node] == 0 or left == right:
        return
 
    mid = (left + right) // 2
    apply(node * 2, left, mid, lazy[node], tree, lazy)
    apply(node * 2 + 1, mid + 1, right, lazy[node], tree, lazy)
    lazy[node] = 0

For a range-sum segment tree, adding delta to every element in a segment increases the stored sum by delta * segment_length. push moves a pending update to children before the algorithm reads or partially updates those children.

Why Delay Work

If an update covers a large interval, updating every leaf would be too slow. Lazy propagation records the update at a higher segment tree node when the whole represented segment is covered.

The children are updated only when a later operation needs to look inside that segment.

Push Down

Pushing down means moving a pending update from a parent to its children:

parent has pending +5
children receive pending +5
parent pending becomes 0

The exact code depends on whether the update is addition, assignment, multiplication, or something else.

Complexity

With correct lazy propagation, range updates and range queries can often be O(log n). The tree and lazy arrays use O(n) space.

A Concrete Mental Model

Imagine an update says “add 5 to this whole segment.” If a query later asks only for the total sum of that exact segment, the tree already knows how the sum changed. It does not need to visit every child.

If a later query asks for only half of that segment, the pending +5 must be pushed to the children so the smaller pieces become accurate.

Lazy propagation is this promise: the stored value is correct for the represented segment, and the children will be corrected before anyone relies on them.

Failure Example

If a range update changes tree[node] but does not record the corresponding lazy[node], a later partial query will descend into children that were never updated.

Lazy propagation is correct only when stored segment values and pending child updates stay consistent.

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.

Another common mistake is updating the stored node value but forgetting to record the lazy value for children. Then future partial queries see stale data.

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.

Do not add lazy propagation for point-update-only problems. A normal segment tree is simpler.

The Main Point

Lazy propagation delays child updates while keeping the parent segment answer correct. The pending value is a promise to fix children before they are used.