Lazy Propagation in Segment Tree using C++
By Keshav JIn this tute, we will discuss Lazy propagation in Segment tree using C++. If you haven’t gone through the basics of implementing segment trees, head straight to sum of range in segment tree before this.
Range updates in Segment Tree:
On the other post on updates in the Segment Tree, we discussed how range updates work on Segment trees. The general idea is that we start from the root of the segment tree and reach the leaves within the given range, change them, return back to the root. In this process, we change a few internal nodes as well.
Let’s see the algorithm we used in the other post:
- Firstly, start with the root.
- Then, at each intermediate node, enter into those child nodes which are within the range.
- If the expected leaves are reached, update them and return to the root.
- While returning to the root, recalculate all the intermediate nodes.
Below is the code snippet used in the other post:
/* Function to update a range of array elements in the Segment
Tree. strt and end are the range in the array. val is the value
to be added. idx is index of node in segment tree. l and r are
the range covered by the node */
void updtRange(int strt, int end, int val, int l, int r, int idx)
{
// Completly ouside the desired range
if(end < l || r < strt || l>r)
return;
// Leaf node reached
if(l == r)
{
tree[idx] += val; // Update the leaves
return;
}
int mid = (l + r) / 2;
updtRange(strt, end, val, l, mid, 2*idx+1);
updtRange(strt, end, val, mid+1, r, 2*idx+2);
// Update the intermediate nodes
tree[idx] = tree[2*idx+1] + tree[2*idx+2];
}
After update,
Here, we can see that if an intermediate node is completely within the range such as node 4:[2,3], all its child nodes are updated as well, that is, all the elements in the range [2,3] are updated. This important observation is key for the optimization done on range updates.
Lazy Propagation in Segment Tree:
Optimization of the range updates by postponing updates at some nodes is referred to as Lazy propagation.
Let’s look into an example. Try to imagine the top view of the tree and enter into the desired nodes only. In the update image, we can see that node 4 in the segment tree having a range [2, 3] has both its children being updated. Later, if a query is done for the range [2, 3], the traversal stops at node 4 because the node is entirely within the desired range. In this scenario, the update operation could’ve been done at node 4 and its children could’ve been updated later. This is because of the fact that in the query operation, we are accessing the node 4 only. What if we could do this for other cases as well?
We can create a new tree named lazy representing the lazy tree. The size and structure of the lazy tree are similar to the original segment tree. The idea here is that while doing update operation if we encounter an intermediate node which is entirely within the range, let’s update that node in the segment tree by using the simple formula,
idx:[l,r] => tree[idx] += ( r - l + 1 ) * val;
Then, postpone the updates of its children by saving those update values in the lazy tree.
The lazy tree is initialized with 0 at the start. If lazy[idx] is 0, then there are no pending updates. Otherwise, all the elements in its range are to be updated with the value lazy[idx].
Algorithm:
updateSegTree(strt, end, val):
1. If lazy[idx] != 0 then
Add the pending update to the current segment tree node
If the node has children, postpone the updates to its children
2. If the current node lies completely within the range then
Update the current node
Postpone the update to its children by adding to lazy nodes of the children
Else
Enter into the child that is within the range
Update the node by recalculating with its child node values after updating
Query Operation: Segment Tree
While in the process of optimizing the range updates, we shouldn’t forget that it’d affect the query method as well. Since we are postponing the updates at a few nodes, we may end up forgetting about those pending updates if we use the old method. So, we must alter the query function as well.
Algorithm:
getSum(strt, end):
1. If lazy[idx] != 0 then
Add the pending update to the current segment tree node
If the node has children, postpone the updates to its children
2. If the current node lies completely within the range then
Return the current node
Else
Enter into the child that is within the range
Update the node by recalculating with its child node values after updatingImplementation:
// C++ program to showLazy propagation in Segment Tree - Sum of range
#include<bits/stdc++.h>
using namespace std;
#define MAX 100010
int tree[MAX], lazy[MAX];
vector<int> ar;
/* Function to display elements of the Segment Tree and
the Lazy tree level by level. */
void showSegTree(int n)
{
int i, j, h = ceil(log2(n));
cout<<"Segment Tree:"<<endl;
for(i=0 ; i<=h ; ++i)
{
for(j=0 ; j<pow(2, i) ; ++j)
cout<<tree[int(pow(2, i)-1 + j)]<<' ';
cout<<endl;
}
cout<<"Lazy Tree:"<<endl;
for(i=0 ; i<=h ; ++i)
{
for(j=0 ; j<pow(2, i) ; ++j)
cout<<lazy[int(pow(2, i)-1 + j)]<<' ';
cout<<endl;
}
}
/* Function to construct the Segment Tree recursively.
At each node, if it is not the leaf, two children are
processed further. Otherwise, the leaf is assigned an
array alement. strt and end are range in the array,
idx is the index used in the segment tree */
int constSegTree(int strt, int end, int idx)
{
// Initialize all lazy tree nodes with 0
lazy[idx] = 0;
// Saves tree[idx] = ar[strt] and then returns tree[idx]
if(strt == end)
return tree[idx] = ar[strt];
int mid = (strt + end) / 2;
return tree[idx] = constSegTree(strt, mid, 2*idx+1) +
constSegTree(mid+1, end, 2*idx+2);
}
void constSegTree(int n)
{
constSegTree(0, n-1, 0);
}
/* Function to get the sum of elements of array in the
range [strt..end]. l & r are the range of current node.
indx is the index of node in segment tree */
int getSum(int strt, int end, int l, int r, int idx)
{
// If there's pending update, update the node first
if(lazy[idx] != 0)
{
// Add the pending update to the current node
// [l..r] contains l-r+1 nodes
tree[idx] += (r-l+1)*lazy[idx];
// If the node has children, postpone the updates
// to the children by adding to the their lazy nodes
if(l != r)
{
lazy[2*idx+1] += lazy[idx];
lazy[2*idx+2] += lazy[idx];
}
// Reset the lazy node of current node
lazy[idx] = 0;
}
// If completly outside the range, don't care
if(end < l || r < strt || l > r)
return 0;
// If node is entirely within the range, return the node value
if(strt <= l && r <= end)
return tree[idx];
// Enter its children and process further
int mid = (l + r) / 2;
return getSum(strt, end, l, mid, 2*idx+1) +
getSum(strt, end, mid+1, r, 2*idx+2);
}
int getSum(int n, int strt, int end)
{
return getSum(strt, end, 0, n-1, 0);
}
/* Function to update a particular node of the array in
Segment Tree. pos is the desired index in the array.
val is the value to be added */
void updtSegTree(int strt, int end, int val, int l, int r, int idx)
{
// If there's pending update, update the node first
if(lazy[idx] != 0)
{
// Add the pending update to the current node
// [l..r] contains l-r+1 nodes
tree[idx] += (r-l+1)*lazy[idx];
// If the node has children, postpone the updates
// to the children by adding to the their lazy nodes
if(l != r)
{
lazy[2*idx+1] += lazy[idx];
lazy[2*idx+2] += lazy[idx];
}
// Reset the lazy node of current node
lazy[idx] = 0;
}
// If completly outside the range, don't care
if(end < l || r < strt || l > r)
return;
// If node is entirely within the range
if(strt <= l && r <= end)
{
// Update the current node in Segment tree
tree[idx] += (r-l+1)*val;
// If the node has children, postpone the updates
// of the children by adding to the their lazy nodes
if(l != r)
{
lazy[2*idx+1] += val;
lazy[2*idx+2] += val;
}
}
else
{
// Enter its children and process further
int mid = (l + r) / 2;
updtSegTree(strt, end, val, l, mid, 2*idx+1);
updtSegTree(strt, end, val, mid+1, r, 2*idx+2);
// Recalculate the itermediate nodes after updation
tree[idx] = tree[2*idx+1] + tree[2*idx+2];
}
}
void updtSegTree(int n, int strt, int end, int val)
{
updtSegTree(strt, end, val, 0, n-1, 0);
}
int main()
{
int n = 7;
ar = {18, 17, 1, 19, 15, 11, 20};
constSegTree(n);
cout<<"n = 7, ar = {18, 17, 1, 19, 15, 11, 20}"<<endl;
showSegTree(n);
updtSegTree(n, 0, 4, 2);
cout<<"\nupdtSegTree(n, 0, 4, 2):"<<endl;
showSegTree(n);
cout<<"\nSum of ar[1..4] = "<<getSum(n, 1, 4)<<endl;
showSegTree(n);
return 0;
}Output:
n = 7, ar = {18, 17, 1, 19, 15, 11, 20}
Segment Tree:
101
55 46
35 20 26 20
18 17 1 19 15 11 0 0
Lazy Tree:
0
0 0
0 0 0 0
0 0 0 0 0 0 0 0
updtSegTree(n, 0, 4, 2):
Segment Tree:
111
63 48
35 20 28 20
18 17 1 19 17 11 0 0
Lazy Tree:
0
0 0
2 2 0 0
0 0 0 0 0 0 0 0
Sum of ar[1..4] = 60
Segment Tree:
111
63 48
39 24 28 20
20 19 1 19 17 11 0 0
Lazy Tree:
0
0 0
0 0 0 0
0 0 2 2 0 0 0 0Bonus: If you still find it difficult to understand the implementation of lazy propagation in segment tree, remove all comments in the code and start tracing for your inputs.
Also, read:
Leave a Reply