Lazy Propagation on segment tree

LAZY PROPAGATION

This is for the update query in the minimum range query question.The brute force method involves
various updates in the segment tree for just one query.However ,in lazy propogation,the update is
only propogated to the child nodes as and when it is required i.e. we maintain another array which
keeps the track of all the previous updates which have not been made yet in the segment tree and
will update only when there is a query on that particular range.


The main idea is to maintain an array lazy of the same size as that of segment tree,and initialize
it to 0.A zero at any position indicates that there are no updates from previous queries and
a non-zero value indicates that there are some updates which have yet not been made on that position
and propagated.

Algorithm to update a range of values.

update(l,r)  //update in range [l-r)
1.if the current segment of tree has any pending update,add that to current node.
2.If current node's range lies completely in
   update query range.
   a) Update current node
   b) Postpone updates to children by setting
       lazy value for children nodes.
3) If current node's range overlaps with update
   range, follow the same approach as above simple
   update.
   a) Recur for left and right children.
   b) Update current node using results of left
      and right calls.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

void updateLazy(int segtree[],int lazy[],int l,int r,int low,int high,int pos,int k) { if(low>high) return; /*make sure all propogation is done at the pos if not update the pos and pass the update to its children*/ if(lazy[pos]!=0) { segtree[pos]+=lazy[pos]; if(low!=high) //if its not a leaf node { lazy[2*pos+1]+=lazy[pos]; lazy[2*pos+2]+=lazy[pos]; } lazy[pos]=0; } //no overlap condition if(l>high||r<low) { return ; } //total overlap else if(l<=low&&r>=high) { segtree[pos]+=k; if(low!=high) //if its not leaf { lazy[2*pos+1]+=k; lazy[2*pos+2]+=k; } return; } else //partial overlap { int mid=(low+high)/2; updateLazy(segtree,lazy,l,r,low,mid,2*pos+1,k); updateLazy(segtree,lazy,l,r,mid+1,high,2*pos+2,k); segtree[pos]=min(segtree[2*pos+1],segtree[2*pos+2]); } }

The above code is for minimum range query question.
Practice more problems on online platform..
HAPPY CODING!