Let's say, you have already created a segment tree. You are required to update the values of the array, this will not only change the leaf nodes of your segment tree, but also the minimum/maximum in some nodes. Let's look at this with an example:
This is our minimum segment tree of 8 elements. To give you a quick reminder, each nodes represent the minimum value of the range mentioned beside them. Let's say, we want to increment the value of the first item of our array by 3. How can we do that? We'll follow the way in which we conducted RMQ. The process would look like:
We can see that, updating a single node requires O(logn)
time complexity, where n is the number of leaf nodes. So if we are asked to update some nodes from i to j, we'll require O(nlogn)
time complexity. This becomes cumbersome for a large value of n. Let's be Lazy i. e., do work only when needed. How? When we need to update an interval, we will update a node and mark its child that it needs to be updated and update it when needed. For this we need an array lazy of the same size as that of a segment tree. Initially all the elements of the lazy array will be 0 representing that there is no pending update. If there is non-zero element in lazy[i], then this element needs to update node i in the segment tree before making any query operations. How are we going to do that? Let's look at an example:
Let's say, for our example tree, we want to execute some queries. These are:
increment [0,3] by 3:
We start from the root node. At first, we check if this value is up-to-date. For this we check our lazy array which is 0, that means the value is up-to-date. [0,3] partially overlaps [0,7]. So we go to both the directions.
Our Segment Tree and Lazy Tree would look like:
The non-zero values in nodes of our Lazy Tree represents, there are updates pending in those nodes and below. We'll update them if required. If we are asked, what is the minimum in range [0,3], we'll come to the left subtree of the root node and since there's no pending updates, we'll return 2, which is correct. So this process doesn't affect the correctness of our segment tree algorithm.
increment [0,3] by 1:
Our Segment Tree and Lazy Tree will look like:
As you can see, we're accumulating the updates at Lazy Tree but not pushing it down. This is what Lazy Propagation means. If we hadn't used it, we had to push the values down to the leaves, which would cost us more unnecessary time complexity.
increment [0,0] by 2:
Our Segment Tree and Lazy Tree will look like:
We can notice that, the value at [0,0], when needed, got all the increment.
Now if you are asked to find the minimum in range [3,5], if you have understood up to this point, you can easily figure out how the query would go and the returned value will be 1. Our segment Tree and Lazy Tree would look like:
We have simply followed the same process we followed in finding RMQ with added constraints of checking the Lazy Tree for pending updates.
Another thing we can do is instead of returning values from each node, since we know what will be the child node of our current node, we can simply check them to find the minimum of these two.
The pseudo-code for updating in Lazy Propagation would be:
Procedure UpdateSegmentTreeLazy(segmentTree, LazyTree, startRange,
endRange, delta, low, high, position):
if low > high //out of bounds
Return
end if
if LazyTree[position] is not equal to 0 //update needed
segmentTree[position] := segmentTree[position] + LazyTree[position]
if low is not equal to high //non-leaf node
LazyTree[2 * position + 1] := LazyTree[2 * position + 1] + delta
LazyTree[2 * position + 2] := LazyTree[2 * position + 2] + delta
end if
LazyTree[position] := 0
end if
if startRange > low or endRange < high //doesn't overlap
Return
end if
if startRange <= low && endRange >= high //total overlap
segmentTree[position] := segmentTree[position] + delta
if low is not equal to high
LazyTree[2 * position + 1] := LazyTree[2 * position + 1] + delta
LazyTree[2 * position + 2] := LazyTree[2 * position + 2] + delta
end if
Return
end if
//if we reach this portion, this means there's a partial overlap
mid := (low + high) / 2
UpdateSegmentTreeLazy(segmentTree, LazyTree, startRange,
endRange, delta, low, mid, 2 * position + 1)
UpdateSegmentTreeLazy(segmentTree, LazyTree, startRange,
endRange, delta, mid + 1, high, 2 * position + 2)
segmentTree[position] := min(segmentTree[2 * position + 1],
segmentTree[2 * position + 2])
And the pseudo-code for RMQ in Lazy Propagation will be:
Procedure RangeMinimumQueryLazy(segmentTree, LazyTree, qLow, qHigh, low, high, position):
if low > high
Return infinity
end if
if LazyTree[position] is not equal to 0 //update needed
segmentTree[position] := segmentTree[position] + LazyTree[position]
if low is not equal to high
segmentTree[position] := segmentTree[position] + LazyTree[position]
if low is not equal to high //non-leaf node
LazyTree[2 * position + 1] := LazyTree[2 * position + 1] + LazyTree[position]
LazyTree[2 * position + 2] := LazyTree[2 * position + 2] + LazyTree[position]
end if
LazyTree[position] := 0
end if
if qLow > high and qHigh < low //no overlap
Return infinity
end if
if qLow <= low and qHigh >= high //total overlap
Return segmentTree[position]
end if
//if we reach this portion, this means there's a partial overlap
mid := (low + high) / 2
Return min(RangeMinimumQueryLazy(segmentTree, LazyTree, qLow, qHigh,
low, mid, 2 * position + 1),
RangeMinimumQueryLazy(segmentTree, LazyTree, qLow, qHigh,
mid + 1, high, 2 * position + 1)