Lazy Propagation in Segment Tree | Set 2 | Python3 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 sum of values in a given 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 sum 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 ]
MAX = 1000 NEW_LINE tree = [ 0 ] * MAX ; NEW_LINE lazy = [ 0 ] * MAX ; NEW_LINE def updateRangeUtil ( si , ss , se , us , ue , diff ) : NEW_LINE INDENT if ( lazy [ si ] != 0 ) : NEW_LINE INDENT tree [ si ] += lazy [ si ] ; NEW_LINE if ( ss != se ) : NEW_LINE INDENT lazy [ si * 2 + 1 ] += lazy [ si ] ; NEW_LINE lazy [ si * 2 + 2 ] += lazy [ si ] ; NEW_LINE DEDENT lazy [ si ] = 0 ; NEW_LINE DEDENT if ( ss > se or ss > ue or se < us ) : NEW_LINE INDENT return ; NEW_LINE DEDENT if ( ss >= us and se <= ue ) : NEW_LINE INDENT tree [ si ] += diff ; NEW_LINE if ( ss != se ) : NEW_LINE INDENT lazy [ si * 2 + 1 ] += diff ; NEW_LINE lazy [ si * 2 + 2 ] += diff ; NEW_LINE DEDENT return ; NEW_LINE DEDENT mid = ( ss + se ) // 2 ; NEW_LINE updateRangeUtil ( si * 2 + 1 , ss , mid , us , ue , diff ) ; NEW_LINE updateRangeUtil ( si * 2 + 2 , mid + 1 , se , us , ue , diff ) ; NEW_LINE tree [ si ] = max ( tree [ si * 2 + 1 ] , tree [ si * 2 + 2 ] ) ; NEW_LINE DEDENT def updateRange ( n , us , ue , diff ) : NEW_LINE INDENT updateRangeUtil ( 0 , 0 , n - 1 , us , ue , diff ) ; NEW_LINE DEDENT def getSumUtil ( ss , se , qs , qe , si ) : NEW_LINE INDENT if ( lazy [ si ] != 0 ) : NEW_LINE INDENT tree [ si ] += lazy [ si ] ; NEW_LINE if ( ss != se ) : NEW_LINE INDENT lazy [ si * 2 + 1 ] += lazy [ si ] ; NEW_LINE lazy [ si * 2 + 2 ] += lazy [ si ] ; NEW_LINE DEDENT lazy [ si ] = 0 ; NEW_LINE DEDENT if ( ss > se or ss > qe or se < qs ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT if ( ss >= qs and se <= qe ) : NEW_LINE INDENT return tree [ si ] ; NEW_LINE DEDENT mid = ( ss + se ) // 2 ; NEW_LINE return max ( getSumUtil ( ss , mid , qs , qe , 2 * si + 1 ) , getSumUtil ( mid + 1 , se , qs , qe , 2 * si + 2 ) ) ; NEW_LINE DEDENT def getSum ( n , qs , qe ) : NEW_LINE INDENT if ( qs < 0 or qe > n - 1 or qs > qe ) : NEW_LINE INDENT print ( " Invalid ▁ Input " , end = " " ) ; NEW_LINE return - 1 ; NEW_LINE DEDENT return getSumUtil ( 0 , n - 1 , qs , qe , 0 ) ; NEW_LINE DEDENT def constructSTUtil ( arr , ss , se , si ) : NEW_LINE INDENT if ( ss > se ) : NEW_LINE INDENT return ; NEW_LINE DEDENT if ( ss == se ) : NEW_LINE INDENT tree [ si ] = arr [ ss ] ; NEW_LINE return ; NEW_LINE DEDENT mid = ( ss + se ) // 2 ; NEW_LINE constructSTUtil ( arr , ss , mid , si * 2 + 1 ) ; NEW_LINE constructSTUtil ( arr , mid + 1 , se , si * 2 + 2 ) ; NEW_LINE tree [ si ] = max ( tree [ si * 2 + 1 ] , tree [ si * 2 + 2 ] ) ; NEW_LINE DEDENT def constructST ( arr , n ) : NEW_LINE INDENT constructSTUtil ( arr , 0 , n - 1 , 0 ) ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , 2 , 3 , 4 , 5 ] ; NEW_LINE n = len ( arr ) ; NEW_LINE constructST ( arr , n ) ; NEW_LINE updateRange ( n , 0 , 3 , 4 ) ; NEW_LINE print ( getSum ( n , 1 , 4 ) ) ; NEW_LINE DEDENT