Array Range Queries to find the Maximum Armstrong number with updates | Python code to implement above approach ; A utility function to get the middle index of given range . ; Function that return true if num is armstrong else return false ; A recursive function to get the sum of values in the given range of the array . The following are parameters for this function . st -> Pointer to segment tree node -> Index of current node in the segment tree . ss & se -> Starting and ending indexes of the segment represented by current node , i . e . , st [ node ] l & r -> Starting and ending indexes of range query ; If segment of this node is completely part of given range , then return the max of segment . ; If segment of this node does not belong to given range ; If segment of this node is partially the part of given range ; A recursive function to update the nodes which have the given the index in their range . The following are parameters st , ss and se are same as defined above index -> index of the element to be updated . ; update value in array and in segment tree ; Return max of elements in range from index l ( query start ) to r ( query end ) . ; 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 ; 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 max of values in this node ; Function to construct a segment tree from given array . This function allocates memory for segment tree . ; Height of segment tree ; Maximum size of segment tree ; Allocate memory ; Fill the allocated memory st ; Return the constructed segment tree ; Driver code ; Build segment tree from given array ; Print max of values in array from index 1 to 3 ; Update : set arr [ 1 ] = 153 and update corresponding segment tree nodes . ; Find max after the value is updated
import math NEW_LINE def getMid ( s : int , e : int ) -> int : NEW_LINE INDENT return s + ( e - s ) // 2 NEW_LINE DEDENT def isArmstrong ( x : int ) -> bool : NEW_LINE INDENT n = len ( str ( x ) ) NEW_LINE sum1 = 0 NEW_LINE temp = x NEW_LINE while ( temp > 0 ) : NEW_LINE INDENT digit = temp % 10 NEW_LINE sum1 += pow ( digit , n ) NEW_LINE temp //= 10 NEW_LINE DEDENT if ( sum1 == x ) : NEW_LINE INDENT return True NEW_LINE DEDENT return False NEW_LINE DEDENT def MaxUtil ( st , ss , se , l , r , node ) : NEW_LINE INDENT if ( l <= ss and r >= se ) : NEW_LINE INDENT return st [ node ] NEW_LINE DEDENT if ( se < l or ss > r ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT mid = getMid ( ss , se ) NEW_LINE return max ( MaxUtil ( st , ss , mid , l , r , 2 * node + 1 ) , MaxUtil ( st , mid + 1 , se , l , r , 2 * node + 2 ) ) NEW_LINE DEDENT def updateValue ( arr , st , ss , se , index , value , node ) : NEW_LINE INDENT if ( index < ss or index > se ) : NEW_LINE INDENT print ( " Invalid ▁ Input " ) NEW_LINE return NEW_LINE DEDENT if ( ss == se ) : NEW_LINE INDENT arr [ index ] = value NEW_LINE if ( isArmstrong ( value ) ) : NEW_LINE INDENT st [ node ] = value NEW_LINE DEDENT else : NEW_LINE INDENT st [ node ] = - 1 NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT mid = getMid ( ss , se ) NEW_LINE if ( index >= ss and index <= mid ) : NEW_LINE INDENT updateValue ( arr , st , ss , mid , index , value , 2 * node + 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT updateValue ( arr , st , mid + 1 , se , index , value , 2 * node + 2 ) NEW_LINE DEDENT st [ node ] = max ( st [ 2 * node + 1 ] , st [ 2 * node + 2 ] ) NEW_LINE DEDENT return NEW_LINE DEDENT def getMax ( st , n , l , r ) : NEW_LINE INDENT if ( l < 0 or r > n - 1 or l > r ) : NEW_LINE INDENT print ( " Invalid ▁ Input " ) NEW_LINE return - 1 NEW_LINE DEDENT return MaxUtil ( st , 0 , n - 1 , l , r , 0 ) NEW_LINE DEDENT def constructSTUtil ( arr , ss , se , st , si ) : NEW_LINE INDENT if ( ss == se ) : NEW_LINE INDENT if ( isArmstrong ( arr [ ss ] ) ) : NEW_LINE INDENT st [ si ] = arr [ ss ] NEW_LINE DEDENT else : NEW_LINE INDENT st [ si ] = - 1 NEW_LINE DEDENT return st [ si ] NEW_LINE DEDENT mid = getMid ( ss , se ) NEW_LINE st [ si ] = max ( constructSTUtil ( arr , ss , mid , st , si * 2 + 1 ) , constructSTUtil ( arr , mid + 1 , se , st , si * 2 + 2 ) ) NEW_LINE return st [ si ] NEW_LINE DEDENT def constructST ( arr , n ) : NEW_LINE INDENT x = int ( math . ceil ( math . log2 ( n ) ) ) NEW_LINE max_size = 2 * int ( math . pow ( 2 , x ) ) - 1 NEW_LINE st = [ 0 for _ in range ( max_size ) ] NEW_LINE constructSTUtil ( arr , 0 , n - 1 , st , 0 ) NEW_LINE return st NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 192 , 113 , 535 , 7 , 19 , 111 ] NEW_LINE n = len ( arr ) NEW_LINE st = constructST ( arr , n ) NEW_LINE print ( " Maximum ▁ armstrong ▁ number ▁ in ▁ given ▁ range ▁ = ▁ { } " . format ( getMax ( st , n , 1 , 3 ) ) ) NEW_LINE updateValue ( arr , st , 0 , n - 1 , 1 , 153 , 0 ) NEW_LINE print ( " Updated ▁ Maximum ▁ armstrong ▁ number ▁ in ▁ given ▁ range ▁ = ▁ { } " . format ( getMax ( st , n , 1 , 3 ) ) ) NEW_LINE DEDENT