Lazy Propagation

March 2026 · 25 min read

This is the hardest and most important concept in segment trees. If you've understood building, querying, and point updates, you have all the prerequisites. Lazy propagation is the technique that gives us O(log n) range updates, without it, updating an entire range would cost O(n log n).

This post explains lazy propagation from first principles, with extreme detail. We'll build up the idea step by step, trace every operation, and make sure you can implement it confidently.

The Problem: Range Updates Are Slow

Suppose we want to "add 5 to every element from index 1 to index 6" in an 8-element array. With point updates, we'd call update() for each index from 1 to 6, that's 6 separate O(log n) updates = O(n log n) total.

The same problem arises for operations like "set all elements in [l, r] to value v." If the range is large, point-by-point is far too slow.

Yes. That's exactly what lazy propagation does.

The Idea: Deferred Work

The Key Insight

When we do a range update "add delta to all elements in [l, r]," we traverse the tree just like a range query. When we find a node whose range is fully inside [l, r]:

• We immediately update the node's value: tree[node] += delta * (end - start + 1). (If every element in the range gets +delta, the sum increases by delta × range_size.)
• But we don't recurse into the children. Instead, we mark the node with a lazy tag: "this node's children haven't been updated yet. They each need +delta applied."

The children's values are now stale. But we don't care, until someone actually needs to look at them.

The Lazy Array

We maintain a second array, lazy[], the same size as tree[]. lazy[node] stores the pending update that needs to be pushed down to node's children but hasn't been yet.

• lazy[node] = 0: No pending update. Node and children are consistent.
• lazy[node] = d: Node's value is already correct (adjusted for the update), but its children each need +d applied to their values and lazy tags.

The Push-Down Operation

When we need to access a node's children (for a query or update that doesn't fully cover this node's range), we first push down the lazy tag:

void pushDown(int node, int start, int end) {
    if (lazy[node] != 0) {
        // Leaf has no children — nothing to push down to
        if (start == end) { lazy[node] = 0; return; }

        int mid = (start + end) / 2;
        int leftSize  = mid - start + 1;
        int rightSize = end - mid;

        // Update left child's value and lazy tag
        tree[2*node]   += lazy[node] * leftSize;
        lazy[2*node]   += lazy[node];

        // Update right child's value and lazy tag
        tree[2*node+1] += lazy[node] * rightSize;
        lazy[2*node+1] += lazy[node];

        // Clear this node's lazy (it's been pushed down)
        lazy[node] = 0;
    }
}

After push-down, the node's children have correct values (for queries) and carry their own lazy tags (for further push-downs if needed).

Range Update with Lazy Propagation

The Algorithm

To add delta to all elements in [l, r]:

1. No overlap (node's range is entirely outside [l, r]): Do nothing. Return.
2. Total overlap (node's range is entirely inside [l, r]): Update the node's value directly. Store the lazy tag. Don't recurse.
3. Partial overlap: First, push down any existing lazy tag (settle existing IOUs). Then recurse into both children. After recursion, recalculate this node from its children.

The Complete Code

void rangeUpdate(int node, int start, int end,
                 int l, int r, int delta) {
    // Case 1: No overlap
    if (r < start || end < l) return;

    // Case 2: Total overlap
    if (l <= start && end <= r) {
        tree[node] += delta * (end - start + 1);
        lazy[node] += delta;
        return;
    }

    // Case 3: Partial overlap — push down first!
    pushDown(node, start, end);

    int mid = (start + end) / 2;
    rangeUpdate(2 * node,     start, mid,     l, r, delta);
    rangeUpdate(2 * node + 1, mid + 1, end,   l, r, delta);

    // Recalculate from children
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

Why Push Down on Partial Overlap?

When we recurse into children, their values need to be correct. If this node has a lazy tag, the children's values are stale. Push-down fixes them before we touch them. Without this step, queries through partially-overlapping nodes would return wrong results.

Why delta × (end - start + 1)?

This is the most important line in lazy propagation, and it's specific to range-sum. Let's understand why:

A node stores the sum of all elements in its range. If we add delta to every element in a range of size k = end - start + 1, the sum increases by delta × k:

// Before: sum = a₁ + a₂ + ... + aₖ
// After:  sum = (a₁+d) + (a₂+d) + ... + (aₖ+d)
//             = (a₁ + a₂ + ... + aₖ) + k × d
//             = old_sum + delta × range_size

This is why we can update a node's value without visiting its children — we know exactly how much the sum changes from the delta and the range size alone.

Querying with Lazy Propagation

Queries also need to push down lazy tags before recursing. The logic is almost identical to the standard query, with one addition:

int queryLazy(int node, int start, int end, int l, int r) {
    // No overlap
    if (r < start || end < l) return 0;

    // Total overlap — value is already correct (lazy accounted for)
    if (l <= start && end <= r) return tree[node];

    // Partial overlap — push down before recursing
    pushDown(node, start, end);

    int mid = (start + end) / 2;
    return queryLazy(2 * node, start, mid, l, r)
         + queryLazy(2 * node + 1, mid + 1, end, l, r);
}

On total overlap, we can return tree[node] directly, the lazy tag has already been factored into this node's value. We only push down when we need to go deeper.

Walkthrough

Step through a complete example: start with arr = [1, 3, 5, 7], apply two range updates, then a query. Watch how lazy tags (purple) defer work and push-down (orange) happens only when children are actually needed.

When Exactly to Push Down

The rule is simple: push down before accessing children. This happens in two places:

1. During a query with partial overlap, before recursing into children.
2. During a range update with partial overlap, before recursing into children.

You do NOT push down when:

• The node has total overlap (you use/update the node's value directly and stop).
• The node has no overlap (you skip it entirely).

This selective push-down is what makes lazy propagation efficient. We only do work when a query or update actually needs to see the children's values.

Complexity Analysis

Range Update: O(log n)

Same argument as range queries. At each tree level, at most 2 nodes have partial overlap. For these, we push down (O(1) work) and recurse. Total-overlap nodes stop immediately. No-overlap nodes are skipped. Total: O(log n).

Range Query: O(log n)

Same as before, with push-down added at partial-overlap nodes. Push-down is O(1). Total: O(log n).

Space: O(n)

The lazy[] array is the same size as tree[], O(4n). Total space: O(n).

Lazy Propagation for Other Operations

The delta × range_size formula only works for sum + range-add. Different query/update combinations require different apply logic. The key question is always: can I compute the new node value from the old value, the lazy delta, and the range size — without visiting children?

This is the single most important thing to internalize: the apply function changes with every (query type, update type) pair. Blindly using delta × range_size everywhere is a common mistake. Let's go through each combination.

Range Add + Min Query

If we add delta to every element in a range, the minimum also increases by exactly delta (no multiplication by range size!):

// Apply: just add delta (not delta × size)
void apply(int node, int s, int e, long long val) {
    tree[node] += val;   // min shifts by delta
    lazy[node] += val;   // compose: lazy tags add
}

// Merge: take the min of children
tree[node] = min(tree[2*node], tree[2*node+1]);

Range Add + Max Query

Identical reasoning to min. Adding delta to every element shifts the maximum by exactly delta:

// Apply: just add delta (not delta × size)
void apply(int node, int s, int e, long long val) {
    tree[node] += val;   // max shifts by delta
    lazy[node] += val;   // compose: lazy tags add
}

// Merge: take the max of children
tree[node] = max(tree[2*node], tree[2*node+1]);

Range Set + Min Query

Set all elements in a range to v. If all elements equal v, the min is just v:

void apply(int node, int s, int e, long long val) {
    tree[node] = val;       // min of all-same elements = val
    lazy[node] = val;
    hasLazy[node] = true;   // flag needed since val could be 0
}

tree[node] = min(tree[2*node], tree[2*node+1]);

Range Set + Max Query

Same idea: if all elements are set to v, the max is v:

void apply(int node, int s, int e, long long val) {
    tree[node] = val;       // max of all-same elements = val
    lazy[node] = val;
    hasLazy[node] = true;   // flag needed since val could be 0
}

tree[node] = max(tree[2*node], tree[2*node+1]);

Range Add + GCD Query

This one is tricky — naive lazy propagation does NOT work. Adding delta to every element doesn't give you a simple formula for the new GCD:

// gcd(a₁+d, a₂+d, ..., aₖ+d) = ???
// There's no formula using just gcd(a₁,...,aₖ) and d.
// Example: gcd(6, 10) = 2, but gcd(6+3, 10+3) = gcd(9, 13) = 1

So you cannot do range-add with GCD queries using standard lazy propagation. You'd need to either:

• Use the identity gcd(a, b) = gcd(a, b-a) and store differences instead (a well-known trick), or
• Use a different data structure (like sqrt decomposition with brute-force rebuild).

Range Set + GCD Query

This does work! If all elements are set to v, the GCD is simply v:

void apply(int node, int s, int e, long long val) {
    tree[node] = val;       // gcd of all-same elements = val
    lazy[node] = val;
    hasLazy[node] = true;
}

tree[node] = __gcd(tree[2*node], tree[2*node+1]);

Why the Formula Changes: An Intuitive Summary

The apply formula depends on how the aggregate (sum, min, max, gcd) responds to a uniform shift of all elements:

For range-set (assign all elements to v), the story is simpler: sum becomes v × k, and min/max/gcd all become v.

The General Pattern

For lazy propagation to work, you need three things:

Range Set (assign) + Sum Query

Instead of "add delta to range," sometimes you want "set all elements in range to value v." The lazy tag stores the value to assign. Push-down overwrites (not adds to) children's values:

// Range assign: set all elements in [l,r] to val
void rangeSet(int node, int s, int e, int l, int r, int val) {
    if (r < s || e < l) return;
    if (l <= s && e <= r) {
        tree[node] = val * (e - s + 1);
        lazy[node] = val;
        hasLazy[node] = true;  // need a flag since val could be 0
        return;
    }
    pushDown(node, s, e);
    int mid = (s + e) / 2;
    rangeSet(2*node, s, mid, l, r, val);
    rangeSet(2*node+1, mid+1, e, l, r, val);
    tree[node] = tree[2*node] + tree[2*node+1];
}

Note: for range-set, the push-down overwrites the child's value and lazy, not adds. And you need a hasLazy flag because the assigned value might be 0.

Handling Both Add and Set

Some problems require both operations. The interaction is tricky: if a node has a pending "set" and then gets an "add," the add modifies the set value. If it has a pending "add" and gets a "set," the add is discarded. This requires careful ordering in push-down. It's an advanced topic, for most problems, you only need one type.

Complete Implementation

class LazySegTree {
    int n;
    vector<long long> tree, lazy;

    void build(const vector<int>& arr, int node, int s, int e) {
        lazy[node] = 0;
        if (s == e) { tree[node] = arr[s]; return; }
        int mid = (s + e) / 2;
        build(arr, 2*node, s, mid);
        build(arr, 2*node+1, mid+1, e);
        tree[node] = tree[2*node] + tree[2*node+1];
    }

    void pushDown(int node, int s, int e) {
        if (lazy[node] != 0) {
            int mid = (s + e) / 2;
            apply(2*node,   s, mid,     lazy[node]);
            apply(2*node+1, mid+1, e,   lazy[node]);
            lazy[node] = 0;
        }
    }

    void apply(int node, int s, int e, long long val) {
        tree[node] += val * (e - s + 1);
        lazy[node] += val;
    }

    void update(int node, int s, int e, int l, int r, long long val) {
        if (r < s || e < l) return;
        if (l <= s && e <= r) { apply(node, s, e, val); return; }
        pushDown(node, s, e);
        int mid = (s + e) / 2;
        update(2*node, s, mid, l, r, val);
        update(2*node+1, mid+1, e, l, r, val);
        tree[node] = tree[2*node] + tree[2*node+1];
    }

    long long query(int node, int s, int e, int l, int r) {
        if (r < s || e < l) return 0;
        if (l <= s && e <= r) return tree[node];
        pushDown(node, s, e);
        int mid = (s + e) / 2;
        return query(2*node, s, mid, l, r)
             + query(2*node+1, mid+1, e, l, r);
    }

public:
    LazySegTree(const vector<int>& arr)
        : n(arr.size()), tree(4*n, 0), lazy(4*n, 0) {
        build(arr, 1, 0, n-1);
    }

    // Add val to all elements in [l, r]
    void update(int l, int r, long long val) {
        update(1, 0, n-1, l, r, val);
    }

    // Query sum of elements in [l, r]
    long long query(int l, int r) {
        return query(1, 0, n-1, l, r);
    }
};

Common Bugs

• Forgetting to push down: The #1 bug. If you recurse into children without pushing down first, you get wrong answers. Always push down at partial-overlap nodes.
• Forgetting to recalculate parent: After updating children, the parent's value must be recalculated. Forgetting this makes subsequent queries return stale values.
• Wrong range size in update: When applying a lazy update, use delta * (end - start + 1), not just delta. The node's value is the sum of the range, not a single element.
• Push-down at leaves: Leaves have no children. Push-down at a leaf is a no-op. Add a if (start == end) return; guard at the top of pushDown() to avoid writing to out-of-bounds child indices.
• Integer overflow: With range updates, values can get large fast. Use long long for both tree[] and lazy[].

Mental Model

Think of lazy propagation as a top-down promise system:

• A range update is like a manager telling a department: "Everyone gets a raise." The manager records it (lazy tag) but doesn't individually notify each employee.
• When someone asks "what's Alice's salary?" (a query that reaches Alice's node), the system pushes the promise down through the chain: department → team → individual. Each level only learns about the raise when they need to.
• Multiple promises can stack: "raise of 5" + "raise of 3" = "pending raise of 8." They're all resolved at once when push-down happens.

This "just-in-time" resolution is why lazy propagation is efficient: we only do work that's actually needed for the current operation.

Summary

• Lazy propagation gives O(log n) range updates by deferring work to children until they're actually needed.
• Each node has a lazy tag storing the pending update for its children.
• Push-down transfers the lazy tag to children before accessing them. It's O(1) per node.
• The tree[node] value is always correct, lazy only affects children.
• Push down only on partial overlap. Total overlap and no overlap don't need it.
• Works for range-add, range-set, and other composable operations.
• The most common bug is forgetting to push down before recursing.