Segment Tree 2: Interval Update and Lazy Propagation

This article explains interval update and lazy propagation of segment tree, including insight and operations in detail.

This article will cover interval update, which is another typical application of segment tree. Interval update allows update queries to be applied to an entire interval of contiguous elements, with a time complexity of O(log n).

It should be noted that single-point update can be considered as a subproblem of interval update, as discussed in the previous article.

Problem

Assuming there is a very large array, two operations need to be performed repeatedly many times on the elements of this array.

• Query: Select an interval in this array and find the sum of all elements in this interval.

• Update: add a value k to all elements within the closed interval [L, R].

The easiest way is to regard it as several single-point updates. As explained in the previous article, the time complexity of a single-point update is O(log n).

However, if we use this method for interval updates, the time complexity degenerates to O(n log n), which is unacceptable.

Insight

For example, consider the interval [3, 6]. We can split it into two sub-intervals: [3, 4] and [5, 6], corresponding to node numbers 5 and 6. Therefore, we only need to update these nodes and postpone updates to their children by storing this update information in a separate data structure called a “lazy array”. This technique is known as “lazy propagation”.

As a result, there is no need to update nodes 10, 11, 12, and 13, as shown in the purple circle in Figure 1, which reduces the time complexity of the algorithm.

Figure 1: Insight

To improve efficiency, we can postpone some updates and avoid recursive calls in update functions. We can then perform these updates only when required.

The segment tree creatively uses lazy tags to implement interval updates. When we need to update an interval, we divide this large interval into several small parts and only modify these parts each time.

Because one interval can be divided into at most O(log n) small intervals, we can complete the interval update in O(log n) time.

Implementation

We can create an array called lazy which stores lazy information. The size of lazy is the same as the array sum that represents the segment tree.

Note that if you encounter integer overflow in C++, you should change int to long long.

At the beginning, we initialize all elements of lazy as 0.

• A value of 0 in lazy[i] indicates that there are no pending updates on node i in the segment tree.

• A non-zero value of lazy[i] means that this value needs to be updated to its children in the segment tree before making any query to the node.

The initial situation is shown in the Figure 2:

Figure 2: lazy array

Update

Figure 3 is the algorithm. They are respectively single-point update (which was discussed in the previous article, just leaving it here for comparison) and interval update.

The push_down function is used to push update information down to child nodes, while the update_one_node function is used to update a single node. The push_up function is used to update parent nodes based on changes in child nodes.

Figure 3

For example, if we want to add 5 to all elements within the interval [3,7], we can use Lazy propagation to split [3,7] into [3,4], [5,6], [7,7], corresponding to nodes 5, 6, and 14 (as indicated by the red circle in the picture). Therefore, we only need to modify these nodes and defer updates to their children by storing this update information in the lazy array.

• At the beginning, we call the update(1, 1, n, 3, 7, 5) function. It is found that [L, R] is not contained by [ql, qr], so if(ql <= L and qr <= R) condition is not met. As a result, we push down the previous lazy information and compute mid = 4, and then go to the left child of the root.

• When it reaches node number 2, according to the code, it enters the right child at this point.

• When it comes to node number 5, if(ql <= L and qr <= R) is satisfied, we only update node number 5(lazy[5] = 5) , the length of this interval is 2, so the value added is 5 * 2 = 10 , and then return directly. Other branches can also follow this algorithm.

• When it returns to the parent node, it uses the push_up function to update the parent node information.

• Other branches can also follow this algorithm and use the push_up function to update the parent node information.

• Finally, the update is applied to the root node.

It can be observed that single-point updates are made at the leaf node, while interval updates store update information in the lazy array and do not require traversal to the leaf node.

Query

For query operation, Figure 3 is the algorithm, they are respectively single-point query (which was discussed in the previous article, just leaving it here for comparison) and interval query.

Figure 4

The only difference between the two functions is that interval query uses pushdown.

We found that although the information of node number 5 has been modified after update operation, its two child nodes(node number 10 and 11) have not been updated .

But don’t worry, even though the modification has not been carried out yet. We will use the “lazy” tag to modify the information of these two sub-nodes when we want to query their information. This ensures that the query results remain accurate.

Figure 5: query the sum of [3, 3]

As shown in Figure 5, for instance, if we want to query the sum of the closed interval [3, 3], we first find the [3,4] through recursion. This interval is not our target interval and there are still lazy tags on this interval, we push down the lazy information. We update the information on the two subintervals of the interval and clear the lazy tags on the interval.

As a result, the values of node number 10 and 11 become the latest values, and the query results are accurate, which is 7 + 5 = 12.

Conclusion

This article explains interval update and lazy propagation of a segment tree. Instead of changing all nodes in the segment tree that cover the query range, we only change some and leave others unchanged. In a sense, we are “lazy” and delay adding the new value to all those nodes until it becomes necessary.

When we need to update an interval, we divide this large interval into at most O(log n) small parts and only modify these parts each time, we can complete the interval update in O(log n) time. Actually, this is similar to Binary Indexed tree‘s lowbit algorithm.

Finally, if there are any omissions or errors in this article, please kindly advise me. Thank you.