8.15 Lazy Propagation

Segment Trees provide efficient range queries and point updates.

algorithmstreesdata-structures

8.15 Lazy Propagation

Segment Trees provide efficient range queries and point updates.

However, some workloads involve large range updates.

Examples include:

  • Increase all salaries in a department.
  • Add a bonus to every employee in a division.
  • Update all values in a subtree.
  • Mark an entire directory as archived.
  • Apply a discount to every product in a category.

A standard Segment Tree handles point updates efficiently, but updating an entire range requires touching every affected element.

Consider:

Add 5 to positions [100,100000]

Updating each element individually destroys the logarithmic performance that made Segment Trees attractive in the first place.

Lazy Propagation solves this problem by postponing work until it becomes necessary.

Instead of immediately updating every descendant, the tree records a pending operation and applies it only when that information is actually needed.

This idea transforms expensive range updates into logarithmic-time operations.

Problem

You need both:

  • Range updates
  • Range queries

and a standard Segment Tree is too slow because updates affect many elements.

Solution

Store pending updates inside internal nodes.

Consider:

Array:
1 2 3 4 5 6 7 8

Suppose we perform:

Add 10 to [0,7]

A normal implementation updates every leaf.

A Lazy Segment Tree updates only the root.

              [0,7]
            +10 pending

No descendants are touched.

The update is remembered rather than executed.

Only when a query or deeper update requires access to a child does the pending value move downward.

This deferred execution is called lazy propagation.

Discussion

The central idea is simple:

Do not perform work until someone actually needs the result.

Suppose we execute:

Add 10 to entire array

followed by:

Sum entire array

Updating every leaf is unnecessary.

The root already knows:

array size × 10

and can adjust its stored sum immediately.

The descendants remain untouched.

This observation is what makes lazy propagation efficient.

Data Structure

A Lazy Segment Tree stores two arrays.

type LazySegmentTree struct {
    tree []int
    lazy []int
    n    int
}

The arrays serve different purposes.

tree

contains actual aggregate values.

lazy

contains pending updates that have not yet been pushed downward.

This separation is crucial.

Building the Tree

Construction is identical to an ordinary Segment Tree.

func build(
    values []int,
    tree []int,
    node int,
    left int,
    right int,
) {
    if left == right {
        tree[node] = values[left]
        return
    }

    mid := (left + right) / 2

    build(
        values,
        tree,
        node*2,
        left,
        mid,
    )

    build(
        values,
        tree,
        node*2+1,
        mid+1,
        right,
    )

    tree[node] =
        tree[node*2] +
        tree[node*2+1]
}

The difference appears during updates.

Propagating Updates

Suppose:

lazy[node] = 5

This means:

Every descendant
should eventually
receive +5

Before exploring children, push the update downward.

func push(
    node int,
    left int,
    right int,
    tree []int,
    lazy []int,
) {
    if lazy[node] == 0 {
        return
    }

    pending := lazy[node]

    tree[node] +=
        (right-left+1) *
        pending

    if left != right {
        lazy[node*2] += pending
        lazy[node*2+1] += pending
    }

    lazy[node] = 0
}

The node absorbs the update.

The children inherit responsibility.

The pending marker disappears from the current node.

Range Updates

Suppose:

Add 5 to [2,6]

Three cases occur.

No Overlap

Node interval:
[0,1]

Query interval:
[2,6]

Ignore it.

Complete Overlap

Node interval:
[2,6]

Store the update lazily.

lazy[node] += 5

No recursion is needed.

Partial Overlap

Split the operation.

Implementation:

func update(
    node int,
    left int,
    right int,
    ql int,
    qr int,
    delta int,
    tree []int,
    lazy []int,
) {
    push(
        node,
        left,
        right,
        tree,
        lazy,
    )

    if qr < left || right < ql {
        return
    }

    if ql <= left &&
       right <= qr {
        lazy[node] += delta

        push(
            node,
            left,
            right,
            tree,
            lazy,
        )

        return
    }

    mid := (left + right) / 2

    update(
        node*2,
        left,
        mid,
        ql,
        qr,
        delta,
        tree,
        lazy,
    )

    update(
        node*2+1,
        mid+1,
        right,
        ql,
        qr,
        delta,
        tree,
        lazy,
    )

    tree[node] =
        tree[node*2] +
        tree[node*2+1]
}

The recursion touches only logarithmically many nodes.

Range Queries

Queries must also honor pending updates.

Before using a node:

push(
    node,
    left,
    right,
    tree,
    lazy,
)

This guarantees the stored value is current.

Query logic then proceeds exactly as in a normal Segment Tree.

func query(
    node int,
    left int,
    right int,
    ql int,
    qr int,
    tree []int,
    lazy []int,
) int

The only additional requirement is processing pending updates first.

Visual Example

Suppose:

Array:
1 2 3 4 5 6 7 8

Perform:

Add 10 to [0,7]

Without lazy propagation:

Update all eight leaves.

With lazy propagation:

Root stores:
pending +10

Now perform:

Sum [0,7]

The answer is immediately available.

No child nodes are visited.

The deferred update never needed to be expanded.

This is where the efficiency comes from.

Why Lazy Propagation Works

Consider a complete overlap.

Node interval:
[0,999]

Update:

Add 5 to [0,999]

Every element changes.

However:

sum += 1000 × 5

can be computed instantly.

The exact distribution among descendants is irrelevant until a future operation requires it.

Lazy propagation exploits this observation.

It stores intent rather than execution.

Euler Tour and Subtree Updates

Lazy Segment Trees pair naturally with Euler Tours.

Suppose:

Subtree(5)

becomes:

[100,250]

in Euler order.

The operation:

Increase every node
in subtree(5)
by 7

becomes:

update(
    100,
    250,
    7
)

No tree traversal is required.

This pattern appears frequently in:

  • Organizational hierarchies
  • File systems
  • Network management
  • Competitive programming

The original tree becomes an interval.

The Lazy Segment Tree handles the interval efficiently.

Assignment Updates

Addition is not the only supported operation.

Suppose:

Set every value
in [l,r]
to 10

This is a different type of update.

The lazy information must now store:

pending assignment

rather than:

pending addition

The propagation logic changes slightly.

The overall idea remains identical.

Many real systems support multiple update types simultaneously.

Multiple Lazy Operations

Advanced implementations may support:

  • Add
  • Assign
  • Multiply

simultaneously.

Now the order of operations matters.

For example:

Assign 10
Then add 5

differs from:

Add 5
Then assign 10

The lazy state must preserve the correct sequence.

Designing these compositions carefully is one of the more advanced aspects of Segment Tree implementations.

Lazy Propagation as Deferred Execution

A useful perspective is to view lazy propagation as a scheduling system.

Instead of:

Execute now.

the tree records:

Execute later
if needed.

This idea appears throughout computer science.

Examples include:

  • Virtual memory
  • Database transactions
  • Build systems
  • Query optimizers
  • JIT compilers

Deferred work often improves efficiency dramatically.

Lazy propagation is a specialized application of the same principle.

Complexity Analysis

Let:

n = number of elements

Building:

Operation Complexity
Build tree O(n)

Queries:

Operation Complexity
Range query O(log n)

Updates:

Operation Complexity
Range update O(log n)

Memory:

Structure Complexity
Tree O(n)
Lazy array O(n)

Without lazy propagation, large range updates often require:

O(n)

work.

With lazy propagation:

O(log n)

becomes possible.

Common Mistakes

A common mistake is forgetting to call:

push(...)

before reading a node.

The stored value may be stale.

Another mistake is updating the children immediately after marking a lazy value. Doing so defeats the entire purpose of deferred execution.

A third mistake is forgetting:

(right-left+1)

when updating sums.

A node represents an interval, not a single element.

The pending update affects every element inside that interval.

Finally, assignment updates and addition updates cannot be combined with identical propagation logic. They require different state-management strategies.

Takeaway

Lazy Propagation extends Segment Trees with deferred execution. Instead of immediately applying updates to every affected element, the tree records pending operations and pushes them downward only when necessary. This transforms expensive range updates into logarithmic-time operations while preserving efficient queries. Combined with Euler Tours, Lazy Segment Trees become one of the most powerful tools for dynamic subtree processing and large-scale hierarchical updates.