Lazy Propagation in Segment Tree | Set 2 | C ++ implementation of the approach ; To store segment tree ; To store pending updates ; si -> index of current node in segment tree ss and se -> Starting and ending indexes of elements for which current nodes stores sum us and ue -> starting and ending indexes of update query diff -> which we need to add in the range us to ue ; If lazy value is non - zero for current node of segment tree , then there are some pending updates . So we need to make sure that the pending updates are done before making new updates . Because this value may be used by parent after recursive calls ( See last line of this function ) ; Make pending updates using value stored in lazy nodes ; Checking if it is not leaf node because if it is leaf node then we cannot go further ; We can postpone updating children we don 't  need their new values now.  Since we are not yet updating children of si,  we need to set lazy flags for the children ; Set the lazy value for current node as 0 as it has been updated ; Out of range ; Current segment is fully in range ; Add the difference to current node ; Same logic for checking leaf node or not ; This is where we store values in lazy nodes , rather than updating the segment tree itelf Since we don 't need these updated values now  we postpone updates by storing values in lazy[] ; If not completely in range , but overlaps recur for children ; And use the result of children calls to update this node ; Function to update a range of values in segment tree us and eu -> starting and ending indexes of update query ue -> ending index of update query diff -> which we need to add in the range us to ue ; A recursive function to get the max of values in given a range of the array . The following are the parameters for this function si -- > Index of the current node in the segment tree Initially , 0 is passed as root is always at index 0 ss & se -- > Starting and ending indexes of the segment represented by current node i . e . , tree [ si ] qs & qe -- > Starting and ending indexes of query range ; If lazy flag is set for current node of segment tree then there are some pending updates . So we need to make sure that the pending updates are done before processing the sub sum query ; Make pending updates to this node . Note that this node represents sum of elements in arr [ ss . . se ] and all these elements must be increased by lazy [ si ] ; Checking if it is not leaf node because if it is leaf node then we cannot go further ; Since we are not yet updating children os si , we need to set lazy values for the children ; Unset the lazy value for current node as it has been updated ; Out of range ; If this segment lies in range ; If a part of this segment overlaps with the given range ; Return max of elements in range from index qs ( querystart ) to qe ( query end ) . It mainly uses getSumUtil ( ) ; Check for erroneous input values ; A recursive function that constructs Segment Tree for array [ ss . . se ] . si is index of current node in segment tree st . ; out of range as ss can never be greater than se ; If there is one element in array , store it in current node of segment tree and return ; If there are more than one elements , then recur for left and right subtrees and store the sum of values in this node ; Function to construct a segment tree from a given array This function allocates memory for segment tree and calls constructSTUtil ( ) to fill the allocated memory ; Fill the allocated memory st ; Driver code ; Build segment tree from given array ; Add 4 to all nodes in index range [ 0 , 3 ] ; Print maximum element in index range [ 1 , 4 ]
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  1000 NEW_LINE int tree [ MAX ] = { 0 } ; int lazy [ MAX ] = { 0 } ; void updateRangeUtil ( int si , int ss , int se , int us , int ue , int diff ) { if ( lazy [ si ] != 0 ) { tree [ si ] += lazy [ si ] ; if ( ss != se ) { lazy [ si * 2 + 1 ] += lazy [ si ] ; lazy [ si * 2 + 2 ] += lazy [ si ] ; } lazy [ si ] = 0 ; } if ( ss > se ss > ue se < us ) return ; if ( ss >= us && se <= ue ) { tree [ si ] += diff ; if ( ss != se ) { lazy [ si * 2 + 1 ] += diff ; lazy [ si * 2 + 2 ] += diff ; } return ; } int mid = ( ss + se ) / 2 ; updateRangeUtil ( si * 2 + 1 , ss , mid , us , ue , diff ) ; updateRangeUtil ( si * 2 + 2 , mid + 1 , se , us , ue , diff ) ; tree [ si ] = max ( tree [ si * 2 + 1 ] , tree [ si * 2 + 2 ] ) ; } void updateRange ( int n , int us , int ue , int diff ) { updateRangeUtil ( 0 , 0 , n - 1 , us , ue , diff ) ; } int getMaxUtil ( int ss , int se , int qs , int qe , int si ) { if ( lazy [ si ] != 0 ) { tree [ si ] += lazy [ si ] ; if ( ss != se ) { lazy [ si * 2 + 1 ] += lazy [ si ] ; lazy [ si * 2 + 2 ] += lazy [ si ] ; } lazy [ si ] = 0 ; } if ( ss > se ss > qe se < qs ) return 0 ; if ( ss >= qs && se <= qe ) return tree [ si ] ; int mid = ( ss + se ) / 2 ; return max ( getSumUtil ( ss , mid , qs , qe , 2 * si + 1 ) , getSumUtil ( mid + 1 , se , qs , qe , 2 * si + 2 ) ) ; } int getMax ( int n , int qs , int qe ) { if ( qs < 0 qe > n - 1 qs > qe ) { printf ( " Invalid ▁ Input " ) ; return -1 ; } return getSumUtil ( 0 , n - 1 , qs , qe , 0 ) ; } void constructSTUtil ( int arr [ ] , int ss , int se , int si ) { if ( ss > se ) return ; if ( ss == se ) { tree [ si ] = arr [ ss ] ; return ; } int mid = ( ss + se ) / 2 ; constructSTUtil ( arr , ss , mid , si * 2 + 1 ) ; constructSTUtil ( arr , mid + 1 , se , si * 2 + 2 ) ; tree [ si ] = max ( tree [ si * 2 + 1 ] , tree [ si * 2 + 2 ] ) ; } void constructST ( int arr [ ] , int n ) { constructSTUtil ( arr , 0 , n - 1 , 0 ) ; } int main ( ) { int arr [ ] = { 1 , 2 , 3 , 4 , 5 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; constructST ( arr , n ) ; updateRange ( n , 0 , 3 , 4 ) ; cout << getSum ( n , 1 , 4 ) ; return 0 ; }