Lazy propagation is an optimization technique for segment tree to delay some of the update queries so that a set of update queries can be performed more efficiently together and thus, reducing the number of operations performed. While working with segment trees if there are multiple queries to update an interval [l,r] of the array, then we use the method of lazy propagation for efficient solution.
Note that this depends on the number and nature of queries provided and hence, for some cases, this may not give any improvement. In general, lazy propagation is a widely used technique and performs well. The overall time complexity of the update() and query() functions of a segment tree remain the same.
Learn about Segment tree in depthTake a look at the naive approach following which we have presented Lazy propagation so that it is intuitive.
Naive Approach
Instead of using the function to update the required nodes for each element present in that range we can slightly modify that function to avoid multiple calls to that function.
Explanation
We enter the function (consider the implementation given below in Example section) after providing the required arguments, the function has three main segments:
1) If the given range to br updated does not coincide with the range represented by the particular node then return. 2) If the node is a leaf node and lies in the given range update it and then reflect the changes in other nodes of the tree. 3) Update the parent node with the help of children nodes in the bottom up fashion.
Example
Update the range [l,r] by adding a value val to every element present in that index range in the given array A[1,2.....N].
/* Modified function to update segment tree for range update in input
array.
curr_ind- index of current node in segment tree
start_ind and end_ind -Starting and ending indexes of elements for
which current nodes stores sum.
start_upt and end_upt - starting and ending indexes of update query
val -> which we need to add in the given range*/
void updateRange(int curr_ind, int start_ind, int end_ind, int start_upt, int end_upt , int val)
{
// out of range
if (start_ind>end_ind|| start_ind>end_upt || end_ind<start_upt)
return ;
// Current node is a leaf node
if (start_ind==end_ind)
{
// Add the value to current node
tree[curr_ind] += value;
return;
}
// If not a leaf node, recur for children.
int mid =(start_ind+end_ind)/2;
updateRangeUtil(curr_index*2+1, start_ind, mid, start_upt,end_upt, val);
updateRangeUtil(curr_index*2+2, mid+1, end_inf,start_upt,end_upt, val);
// Update current node by calling the children
tree[curr_ind] = tree[curr_index*2+1] + tree[curr_index*2+2];
}
Time Complexity
Range updation by calling update function for each and every element takes O(Nlog(N)) as:
- in the worst case there are N elements to be updated
- each update function takes log(N) time
Lazy Propagation (Efficient Approach)
When there are many updates which are to be done on a range, we can postpone some updates (avoid recursive calls in updates) and do them only when required.We do this by creating an array named lazy[], which stores the update information for the tree.
Example
Consider the node with value 7 in below diagram, this node stores sum of values at indexes from 2 to 3. If our update query is for range 2 to 3 and we have to increase them by 4 , then we need to update this node and all descendants of this node. Using Lazy Propagation, we update only node with value 7 to 7+4=11 and store the updates to be done to its children in separate nodes called lazy nodes.The lazy[] array represents lazy node .Size of lazy[] is same as array that represents segment tree.
Theoretical Explanation
Firstly,initialize all elements of lazy[] as 0.It indicates that there are no pending updates on the ith node in segment tree. A non-zero value means that this amount needs to be added to the ith node in segment tree before making any query to the node.
To update an interval we make three cases:
1) If the current node has any pendig updates then firstly add those updates to the lazy node. 2) If the interval represented by current node lies completely in the interval to update, then update the current node and update the lazy[] array for children nodes. 3) If the interval represented by current node overlaps with the interval to update, then- a) Recur for left and right children. b) Update the nodes as the earlier update function.
We also need to update the query() function for any pending updates in the given query.
C++ Implementation of update()
and query()
Implementation of update() function:
//'root' represents the current node
//'start' and 'end' represent the starting and ending indexes of the elements for which current node stores the sum
//'l' and 'r' represnt starting and ending indexes of update query
//'val' represents value which we need to add in the given range
void updateRange(int root, int start, int end, int l,
int r, int val)
{
//The value of lazy node is non-zero so there are some pending updates to be done.Thus, we do these updates first.
if (lazy[root] != 0)
{
// Updating the node by adding the sum of nodes that are common between the query and range represented by that node
tree[root] += (r-l+1)*lazy[root];
if (start != end)
{
//If it is not a leaf node we can postpone the updation of it's children by adding that value to lazy nodes of the children
lazy[root*2 + 1] += lazy[root];
lazy[root*2 + 2] += lazy[root];
}
// Set the lazy value for current node as 0 as it
// has been updated
lazy[root] = 0;
}
// out of range
if (start>end || start>r || end<l)
return ;
// If cuurent segment fully overlaps with the given range
if (start>=l && end<=r)
{
// Add the difference to current node
tree[root] += (end-start+1)*val;
//checking leaf node or not
if (start != end)
{
//We postpone the updation to the children and store the value to be updated in the lazy nodes of the respective children
lazy[root*2 + 1] += val;
lazy[root*2 + 2] += val;
}
return;
}
// If interval does not completely overlaps with the given range recur to the left and right subtree
int mid = (start+end)/2;
updateRangeUtil(root*2+1, start, mid, l, r, val);
updateRangeUtil(root*2+2, mid+1, end, l, r, val);
// Children are used to update the corresponding parent node
tree[root] = tree[root*2+1] + tree[root*2+2];
}
Implementation of query function:
int query(int root, int start, int end, int l, int r)
{
if(start > end or start > r or end < l)
return 0; // Out of range
if(lazy[root] != 0)
{
// This node has pending updations
tree[node] += (end - start + 1) * lazy[node];//updating node
if(start != end)//if it is not the leaf node
{
//The lazy node value after updation of parent is passed to the children whose updation is currently not needed
lazy[root*2+1] += lazy[root];
lazy[root*2+2] += lazy[root];
}
lazy[root] = 0;//lazy node value reset
}
if(start >= l and end <= r)// Current segment is totally within query range
return tree[root];
int mid = (start + end) / 2;
int q1 = queryRange(root*2+1, start, mid, l, r);
int q2 = queryRange(root*2+2, mid + 1, end, l, r);
return (q1 + q2);
}
Question
Construct a segment tree for range addition query for the given array A[]={1,2,3,4,5} and perform following operations-
- 1) Update the interval (0,2) by 3.
- 2) Find sum of index range (1,4)
Happy Coding!
This is a companion discussion topic for the original entry at http://iq.opengenus.org/lazy-propagation-in-segment-tree/