Optimizing a Segment Tree with Lazy Propagation

Reading time: 30 minutes

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.

Take 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!