Lazy Propagation in Segment Tree

Note: This section assumes that you already understand the basics of Segment Trees. If not, please read the Segment Tree explanation first and then come back here.

👉 Go to Segment Tree

What is Lazy Propagation?

Lazy Propagation is an optimization technique used in Segment Trees to efficiently handle range update operations. Instead of updating all elements in a range immediately, updates are delayed and applied only when required.

When is Lazy Propagation Used?

Lazy Propagation is mainly used when we need to perform range-based updates. For example:

Adding a value to all elements in a range [ql, qr]
Assigning a value to all elements in a range
Updating ranges multiple times before querying

Without lazy propagation, these operations would require updating every element in the range, leading to poor performance.

How Does Lazy Propagation Work?

As the name suggests, lazy propagation works by postponing updates. When a range update is applied, the Segment Tree node stores the update value in a separate lazy array instead of immediately updating its children.

For example, if we need to add 7 to the range [5, 8], the node covering this range will store:

lazy[idx] = 7

The actual update is applied only when this segment is required during a query or further traversal.

This avoids unnecessary updates and ensures that operations remain efficient.

Why Prefix Sum Fails for Range Updates

Using a prefix sum array, we can answer range sum queries in O(1) time. However, when an update occurs:

The original array changes
The prefix sum array must be rebuilt
This rebuild takes O(n) time

With many updates, the total time complexity becomes O(q · n), which leads to TLE for large inputs.

How Segment Tree with Lazy Propagation Solves This

A Segment Tree with Lazy Propagation solves this problem efficiently by:

Answering range queries in O(log n)
Handling range updates in O(log n)

Even with a large number of queries, the total time complexity becomes O(q · log n), which is efficient and scalable.

Conclusion

Prefix sums fail when frequent updates are required
Segment Trees handle both queries and updates efficiently
Lazy Propagation is a reliable and scalable solution that optimizes range-based update operations

Lazy propagation turns expensive range updates into efficient operations, making segment trees practical for real competitive programming problems.

Structure of Lazy Propagation

Lazy Propagation is an extension of the Segment Tree that is used when range-based update operations are required. The core structure of the Segment Tree remains the same; lazy propagation only changes how and when updates are applied.

Lazy Array

Along with the segment tree array, an additional array called thelazy array is maintained. This array stores pending updates for segments that have not yet been propagated to their child nodes.

When a range update completely covers a segment, the update is applied to the current node, and the update value is stored in thelazy array. The children are not updated immediately.

Deferred Updates

Updates are intentionally delayed. A segment is only updated when it is required during a query or when further traversal of that segment is necessary. This avoids repeated updates on large ranges.

Lazy propagation postpones updates until they are actually needed, while still keeping the segment tree logically correct.

Propagation Process

Whenever a node is accessed, any pending lazy value stored at that node is first applied. The value is then passed to its children, and the lazy value of the current node is cleared.

This ensures correctness while maintaining logarithmic time complexity.

Construction

The construction of a Segment Tree with Lazy Propagation is identical to a normal Segment Tree. The tree is built using a merge operation, and the lazy array is initialized with zeros.

Time Complexity

Building the tree: O(n)
Range update: O(log n)
Point update: O(log n)
Range query: O(log n)

By deferring updates and applying them only when necessary, Lazy Propagation allows Segment Trees to efficiently handle large numbers of range updates and queries.

Range Sum, Point Update, and Range Update Queries

Range Sum Queries

In a Segment Tree with Lazy Propagation, sum queries are handled similarly to a normal Segment Tree, with one additional step to ensure correctness.

Before using a node’s value, any pending lazy update stored at that node is applied.
If the current segment completely lies inside the query range[ql, qr], its stored sum is returned directly.
If the query range lies entirely in one child, the query is forwarded to that child.
If the query overlaps both children, the range is split, both children are queried recursively, and their results are added.

Since lazy updates are applied only when required and the height of the tree is O(log n), the time complexity of a sum query remains O(log n).

Point Update Queries

A point update modifies a single element in the array. The process is similar to a normal Segment Tree update, with the additional handling of lazy values.

Any pending lazy value at the current node is first applied before moving deeper.
The tree is recursively traversed to reach the leaf node corresponding to the update index.
After updating the leaf node, the changes are propagated upward by recomputing the affected parent nodes.

Only one node per level is updated, so the time complexity of a point update is also O(log n).

Range Update Queries

Range update queries are the main reason for using Lazy Propagation. Instead of updating every element in the range immediately, updates are deferred.

If the current segment lies completely outside the update range, it is ignored.
If the current segment is fully covered by the update range, the node is updated directly and the update value is stored in thelazy array.
If the segment is partially covered, any pending lazy updates are first propagated, and the update is applied recursively to both children.

By postponing updates and applying them only when necessary, range updates are performed in O(log n) time instead of linear time.

This combination of efficient sum queries, point updates, and range updates makes Lazy Propagation essential for handling complex range-based problems efficiently.

Implementation

There are multiple ways to implement a Segment Tree with Lazy Propagation. A commonly used and efficient approach is the array-based representation, where the tree is stored in a flat array. This approach is both time-efficient and space-efficient.

If you want to understand why an array is used to represent a Segment Tree, you can refer to the explanation provided on CP-Algorithms.

Array-Based Representation

The array-based representation for Lazy Propagation is the same as a normal Segment Tree. The only difference is the addition of a separatelazy array to store pending updates.

In this representation, the Segment Tree is stored in an array of size4 * n to safely accommodate all nodes.

The root node is stored at index 0
The left child of a node at index i is at 2 * i + 1
The right child of a node at index i is at 2 * i + 2

This representation allows efficient traversal and updates without using explicit pointers.

📌 Variable Notation

idx → index of the current node in the segment tree array
l → left boundary of the segment represented by the current node
r → right boundary of the segment represented by the current node
ql → left boundary of the query or range update
qr → right boundary of the query or range update
pos → index of the element for a point update
val → value to be added during a point or range update

Build Function

The build function constructs the Segment Tree in the same way as a normal Segment Tree. Leaf nodes store individual array elements, and internal nodes store the merged result of their children. Thelazy array is initialized with zeros.

Push Function

The push function is used to propagate pending lazy values from a parent node to its children. When a node has a non-zero lazy value and we need to access its children (during a query or further update), this value is pushed down to the child nodes.

During the push operation, a pending update stored at a node is propagated to its children. If a node representing the range [l, r] has a lazy valuelazy[idx] = x, then this value is passed down to both child nodes. The left child and right child each accumulate this value in their own lazy entries, and their segment values are updated accordingly.

For example, if a node covering the range[2, 5] has a pending update of+3, this update is not immediately applied to its children. When a push is required, the update is transferred to the children covering [2, 3] and[4, 5]. Each child stores the update in its lazy value, and the parent’s lazy value is then reset.

The push function ensures correctness by applying deferred updates at the right time, while still keeping all operations efficient withO(log n) complexity.

Range Sum Query Function

Range sum queries in a Lazy Segment Tree are conceptually similar to those in a normal Segment Tree, but with an important additional step. In a standard Segment Tree, we can directly use the stored node values because there are no pending updates.

In contrast, a Lazy Segment Tree may contain pending updates stored in thelazy array. Therefore, before using the value of any node, we must first check whether a lazy value exists. If a pending update is found, it is propagated to the child nodes using thepush function, and the current node’s value is updated accordingly.

After ensuring that all pending updates are applied, the query proceeds using the same overlap-based logic as a normal Segment Tree to compute the required range sum.

Point Update Function

In a Lazy Segment Tree, a point update follows the same traversal path as in a normal Segment Tree, but with additional handling for pending updates. Starting from the root, the tree is traversed recursively toward the leaf node that represents the target index.

At each visited node, the algorithm first checks whether there is any pending update stored in the lazy array. If a lazy value exists, it is propagated downward using thepush function so that the current node and its children reflect all deferred updates before continuing the traversal.

Once the traversal reaches the leaf node corresponding to the update index, the node’s value is updated directly. As the recursion unwinds, all ancestor nodes are recomputed using the merge operation (such as summation), ensuring that the changes are correctly reflected throughout the tree.

Range Update Function

The range update function is the core component of a Lazy Segment Tree. Its purpose is to apply an update operation (such as addition or assignment) to all elements within a given range[ql, qr] without explicitly updating every element in that range.

When the current segment[l, r] is completely outside the update range, the function returns immediately, as no update is required. If the segment is fully covered by the update range, the update is applied directly to the node’s stored value, and the update information is recorded in the lazy array. This indicates that the update should be propagated to the children at a later time.

In the case of partial overlap, the algorithm first checks for any pending lazy updates at the current node. If such updates exist, they are propagated downward using the push function to ensure correctness. The update operation is then recursively applied to both child segments, and after the recursion completes, the current node’s value is recomputed using the merge operation.

By deferring updates and propagating them only when necessary, the range update function guarantees that both update and query operations run inO(log n) time, even for large input sizes.

📌 Note: A point update is a special case of a range update where the update range consists of a single index. In other words, when the start and end of the update range are equal, both operations behave identically.

From an implementation perspective, this can be expressed as:

pointUpdate(idx, l, r, pos, val)
is equivalent to
rangeUpdate(idx, l, r, pos, pos, val)

This equivalence highlights that Lazy Propagation generalizes point updates into range updates, allowing both operations to be handled efficiently within a unified framework.

Complete Segment Tree Code

Here is a sample code snippet for Segment Tree with lazy propagation sum operations:

Summary

I have explained Segment Tree with Lazy Propagation based on my own understanding and what I learned while studying them. I hope this guide is helpful. If you find any mistakes or areas for improvement, please feel free to report them.

Practice Problems

You can practice Lazy Propagation–based Segment Tree problems on various competitive programming platforms. Here are a few recommended problems to get you started:

These problems will help you understand the implementation and application of Segment Trees with Lazy Propagation in different scenarios.