A standard segment tree supports point updates in O(log n) and range queries in O(log n). But what about range updates: adding a value to every element in [l, r]?

The naive approach is k individual point updates, costing O(k log n). For k close to n, that is worse than just updating a raw array in O(n).

Lazy propagation brings range updates down to O(log n), matching the range query cost. It builds on a standard segment tree, using the same 1-indexed storage (root at index 1, children at 2*node and 2*node + 1) throughout this chapter.

The Problem

Suppose you have an array of n elements and need to support two operations:

With a basic segment tree, you can query in O(log n), but updating a range means updating each element individually, costing O(n log n) in the worst case. For large ranges, this is terrible.

The Key Insight

Defer the work.

When a range update fully covers a node's segment, mark it with a pending update but do not push the update to its children yet. Only push down ("propagate") when you actually need to access a child. This defers O(n) work until it is needed, and much of it may never be needed at all.

If a later operation never recurses into that subtree before another update overwrites it, the deferred work is dropped entirely. The same idea shows up in write-back caches and copy-on-write: do nothing until something forces you to.

Lazy Markers on a Tree

Here is what a segment tree looks like after a range update with lazy propagation. Some nodes carry "lazy" values, meaning they have pending updates that have not been pushed to their children yet.

The orange nodes have lazy markers. Their children have not been updated yet, but the parent's sum already reflects the pending addition. When we eventually need to access a child, we push the lazy value down at that point.

The Lazy Array

In addition to the tree[] array that stores node values, we maintain a lazy[] array of the same size. Each entry in lazy[] stores the pending update for that node. Initially, all values are 0, meaning no pending updates.

Push Down (Propagate)

Push down is the operation that turns a deferred update into actual values on child nodes. Before accessing any child, we check if the current node has a pending update. If it does, we:

In this example, Node 1 covers a segment of length 3 (indices [0,2]). Its left child covers [0,1] (length 2) and right child covers [2,2] (length 1). When we push down:

The parent's sum does not change during push down. It was already updated when the lazy was first applied.

Range Update

The range update follows the same three-case logic as a range query, with one critical addition: we set lazy markers instead of recursing all the way down.

The total overlap case is what makes range updates O(log n). Instead of recursing into potentially thousands of leaf nodes, we stop at the node that fully covers the update, record a marker, and return.

Range Query

Querying works exactly like the standard segment tree query, with one addition: before recursing into children during a partial overlap, push down the current node's lazy value first. This ensures the children have up-to-date values before we read from them.

Decision Flowchart

Let us work through a concrete example with the array [1, 3, 5, 7, 9, 11] (6 elements, 0-indexed).

Step 1: Build the Segment Tree

Building works exactly as in a standard segment tree. Each leaf holds one element, and internal nodes hold the sum of their children.

Step 2: Range Update, Add 3 to Range [1, 4]

We call updateRange(1, 4, 3). Let us trace through the recursion:

After this update, the tree looks like:

Node [3,4] was totally covered by [1,4], so we stopped there and set its lazy to 3. Nodes [3,3] and [4,4] were never visited; if no future query needs them, the work to apply +3 to those leaves never happens.

Step 3: Range Query, Sum of [2, 5]

We call queryRange(2, 5). Let us trace it:

The answer is 41. Let us verify: the original array was [1, 3, 5, 7, 9, 11], and we added 3 to indices [1,4], giving [1, 6, 8, 10, 12, 11]. Sum of [2,5] = 8 + 10 + 12 + 11 = 41. Correct.

Notice that during this query, we never had to push down any lazy values because we never hit a partial overlap on a node with a pending lazy. The lazy values on [1,1], [2,2], and [3,4] were never disturbed.

Step 4: Second Range Update, Add 2 to Range [0, 2]

Now let us see how lazy values compose. We call updateRange(0, 2, 2):

But wait. Node [1,1] already had lazy=3 from the previous update. And now node [0,2] has lazy=2. What happens when we eventually push down from [0,2]?

When [0,2] pushes down, its children [0,1] and [2,2] each receive lazy += 2. Node [2,2] already has lazy=3, so it will become lazy=5. Node [0,1] had lazy=0 (its children [0,0] and [1,1] handled their own lazy), so it will become lazy=2. Then when [0,1] pushes down, node [1,1] with lazy=3 will receive lazy += 2, becoming lazy=5.

Because addition is associative and commutative, two pending lazy values compose by summing them. The order in which they were applied does not matter.

If we later query a range that forces a push down from [0,2], the lazy values cascade correctly through the tree.

Here is the complete implementation of a segment tree with lazy propagation. It supports range updates and range sum queries, with a lazy array holding pending updates and a pushDown step that propagates them to children only when needed. Comments mark what is NEW compared to a basic segment tree.

Code Explanation

Compared to a basic segment tree, the structural changes here are surprisingly small. The entire technique boils down to two additions: the lazy[] array and the pushDown() function.

How pushDown Works

The pushDown function is called whenever we are about to recurse into a node's children. It checks whether the current node has any pending updates (lazy != 0). If it does:

How Lazy Values Compose

For addition-based lazy propagation, composition is simple: just add the new lazy to the existing one. If a node already has lazy=3 and receives another update of 5, its lazy becomes 8. This works because addition is associative and commutative. Adding 3 then adding 5 is the same as adding 8.

This simplicity is specific to the "add" operation. Other operations like "set to value X" require different composition logic, which we cover in the Variations section.

How Node Values Update During Range Update

When a range update totally covers a node's segment [start, end], the sum increases by val * (end - start + 1). The derivation is one line: each of the (end - start + 1) elements in the segment gains val, so the sum gains val * length. We never need to look at individual element values to perform the update.

Range Update: O(log n)

At each level of the tree, we visit at most 4 nodes (a proof similar to the standard segment tree query applies). The tree has O(log n) levels, so we visit O(log n) nodes. At each node, we do O(1) work (push down, update value, set lazy). Total: O(log n).

Without lazy propagation, updating a range of length k costs O(k log n) because we perform k individual point updates. For k close to n, this degrades to O(n log n), which is no better (and sometimes worse) than updating the raw array.

Range Query: O(log n)

Same analysis as the standard segment tree query. The push down at each node adds O(1) extra work, so the overall complexity remains O(log n).

Space: O(n)

We need two arrays of size 4n: one for the tree and one for the lazy values. Total space is O(n).

Comparison

Where k is the length of the update range. For k = n, the difference is O(n log n) vs O(log n), a dramatic improvement.

Set/Assign Lazy

Instead of adding a value, sometimes you need to set all elements in a range to a specific value. The key difference is in composition: a new "set" operation completely overwrites any pending lazy, whether it was an add or a previous set.

For a set operation:

You can mark "no pending set" two ways. A sentinel like INT_MIN or None works but breaks if the actual data ever contains that value. The cleaner approach is a parallel boolean[] hasLazy array of the same size as lazy[]. hasLazy[node] is true when a set is pending, and lazy[node] holds the value. Push-down checks hasLazy[node], applies the set to children, sets their hasLazy to true, and clears the parent's flag. The extra boolean[] is cheap and removes any restriction on what values you can store.

Multiply Lazy

For multiplication operations (multiply all elements in a range by val):

Composing Different Lazy Operations

Some problems require both addition and multiplication on the same segment tree. This is significantly more complex. You maintain two lazy values per node (one for multiply, one for add) and apply them in a fixed order: multiply first, then add.

When composing, if a new operation is "multiply by m":

If a new operation is "add a":

This composition order matters. Getting it wrong produces subtle bugs.

Lazy Propagation with Min/Max Segment Trees

For min/max queries with range add updates, lazy propagation works similarly. The key difference is in how the node value updates:

The reason the formula is tree[node] += val and not tree[node] += val * length: min and max are translation-invariant under addition. If you add the same constant to every element in a segment, the minimum and maximum of that segment shift by the same constant. Sum, by contrast, is not translation-invariant: adding val to each of length elements increases the sum by val * length. The lazy formula always mirrors how the aggregate responds to a uniform shift.

For range set with min/max:

Comparison of Lazy Operation Types

Pattern 1: Range Add + Range Sum

This is the classic application we have been discussing. Given an array, support adding a value to all elements in a range and querying the sum of a range. Problems like "Range Sum Query" with range updates fall into this category.

Pattern 2: Range Set + Range Query

Assign a value to all elements in a range, then query sum/min/max. This appears in problems involving painting intervals, where you "paint" a range with a color (value) and later ask about the state of a range.

Pattern 3: Interval Painting/Coloring

Given a number line, paint intervals with different colors. Query how many distinct colors exist in a range, or what color a specific point has. This uses lazy propagation with the "set" operation, where painting a range overwrites all previous colors.

Pattern 4: Flip Operations on Binary Arrays

Given a binary array (0s and 1s), support flipping all elements in a range (0 becomes 1, 1 becomes 0) and querying the count of 1s in a range. The lazy value is a boolean flag indicating whether a flip is pending. Composition: two flips cancel out (XOR with 1 twice returns to original).