Before we understand what is lazy propagation, we shall understand the need for lazy propagation.
Consider the array below and the corresponding segment tree for min element range query.
Now suppose you need to increment all the elements from the range [0, 3] by 2, then you need to go till the leaf node and then update all the values as shown below:
After the update you need to calculate the smallest element in all the ranges as shown below:
Here we are updating till the leaf node. Consider that you have a large amount of update query then the performance will take a hit. Hence we are using lazy propagation.
Working of Lazy Propagation:
In lazy propagation we take another array of same length and initialize with NULL or INT_MAX.
When we reach certain index in the segment tree array, we check the value in the lazy tree array. If the value is NULL, we don’t do any operation. If it has other than NULL value, then we update all the children from that part of the index.
We shall look at an example and understand the concept.
We shall perform below operations in segment tree:
increment [0, 3] by 2
increment [0, 3] by 1
increment [1, 1] by 2
search min [3, 4]
- Increment [0, 3] by 2
Initially the segment tree will be like below:
As [0, 5] is a partial overlap for [0, 3], then traverse both left and right.
Now for the left child [0, 3] is a complete overlap for our update query. Now what you need to do is to update the value at that node and then in the lazy array, update the value to be incremented to its children as shown below:
Point to be noted is that we are not updating till the end of the array. We are just updating till we reach the total overlap and stop there and then update the lazy array with the value to be incremented.
- Now increment [0, 3] by 1.
Now also we follow the same steps as above. Increment the segment till [0, 3] range by 1 and then add 1 to its children in the lazy array.
- Now the statement increment [1, 1] by 2
To reach [1, 1] we need to traverse [0, 5], [0, 3], [0, 1], [1,1], [2, 3]. This is shown in below image 52
Now when we reach at the range [0, 1], we check the lazy tree, and see that there is value that is other than NULL. Hence we need to update the value in the segment tree. And send the value of the update to it’s children.
Now update the same for the range [2, 3] and send the value to it’s children.
Now we need to update [1, 1] range. Hence we increment the value of the range [0, 1] in the segment tree.
Note that we are updating [1,1]. Hence we only need to update the children of [0, 1], as [2, 3] is no overlap condition, we don’t need to update it’s children.
- Now for the query [3, 4]
For this the tree traversal will be as below:
As [3, 4] is a partial overlap for [2, 3] we go till the child of [2, 3] and update the value from the lazy propagation tree.
The new tree will be as below:
From the above tree we get the min value in the range [3, 4] which is 4.