Queries to find the minimum index in a range [ L , R ] having at least value X with updates | Python 3 program for the above approach ; Stores nodes value of the Tree ; Function to build segment tree ; Base Case ; Find the value of mid ; Update for left subtree ; Update for right subtree ; Update the value at the current index ; Function for finding the index of the first element at least x ; If current range does not lie in query range ; If current range is inside of query range ; Maximum value in this range is less than x ; Finding index of first value in this range ; Update the value of the minimum index ; Find mid of the current range ; Left subtree ; If it does not lie in left subtree ; Function for updating segment tree ; Update the value , we reached leaf node ; Find the mid ; If pos lies in the left subtree ; pos lies in the right subtree ; Update the maximum value in the range ; Function to print the answer for the given queries ; Build segment tree ; Find index of first value atleast 2 in range [ 0 , n - 1 ] ; Update value at index 2 to 5 ; Find index of first value atleast 4 in range [ 0 , n - 1 ] ; Find index of first value atleast 0 in range [ 0 , n - 1 ] ; Driver Code ; Function Call
maxN = 100 NEW_LINE Tree = [ 0 for i in range ( 4 * maxN ) ] NEW_LINE def build ( arr , index , s , e ) : NEW_LINE INDENT global Tree NEW_LINE global max NEW_LINE if ( s == e ) : NEW_LINE INDENT Tree [ index ] = arr [ s ] NEW_LINE DEDENT else : NEW_LINE INDENT m = ( s + e ) // 2 NEW_LINE build ( arr , 2 * index , s , m ) NEW_LINE build ( arr , 2 * index + 1 , m + 1 , e ) NEW_LINE Tree [ index ] = max ( Tree [ 2 * index ] , Tree [ 2 * index + 1 ] ) NEW_LINE DEDENT DEDENT def atleast_x ( index , s , e , ql , qr , x ) : NEW_LINE INDENT global Tree NEW_LINE global max NEW_LINE if ( ql > e or qr < s ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT if ( s <= ql and e <= qr ) : NEW_LINE INDENT if ( Tree [ index ] < x ) : NEW_LINE INDENT return - 1 ; NEW_LINE DEDENT while ( s != e ) : NEW_LINE INDENT m = ( s + e ) // 2 NEW_LINE if ( Tree [ 2 * index ] >= x ) : NEW_LINE INDENT e = m NEW_LINE index = 2 * index NEW_LINE DEDENT else : NEW_LINE INDENT s = m + 1 NEW_LINE index = 2 * index + 1 NEW_LINE DEDENT DEDENT return s NEW_LINE DEDENT m = ( s + e ) // 2 NEW_LINE val = atleast_x ( 2 * index , s , m , ql , qr , x ) NEW_LINE if ( val != - 1 ) : NEW_LINE INDENT return val NEW_LINE DEDENT return atleast_x ( 2 * index + 1 , m + 1 , e , ql , qr , x ) NEW_LINE DEDENT def update ( index , s , e , new_val , pos ) : NEW_LINE INDENT global Tree NEW_LINE global max NEW_LINE if ( s == e ) : NEW_LINE INDENT Tree [ index ] = new_val NEW_LINE DEDENT else : NEW_LINE INDENT m = ( s + e ) // 2 NEW_LINE if ( pos <= m ) : NEW_LINE INDENT update ( 2 * index , s , m , new_val , pos ) NEW_LINE DEDENT else : NEW_LINE INDENT update ( 2 * index + 1 , m + 1 , e , new_val , pos ) NEW_LINE DEDENT Tree [ index ] = max ( Tree [ 2 * index ] , Tree [ 2 * index + 1 ] ) NEW_LINE DEDENT DEDENT def printAnswer ( arr , n ) : NEW_LINE INDENT global Tree NEW_LINE global max NEW_LINE build ( arr , 1 , 0 , n - 1 ) NEW_LINE print ( atleast_x ( 1 , 0 , n - 1 , 0 , n - 1 , 2 ) ) NEW_LINE arr [ 2 ] = 5 NEW_LINE update ( 1 , 0 , n - 1 , 5 , 2 ) NEW_LINE print ( atleast_x ( 1 , 0 , n - 1 , 0 , n - 1 , 4 ) ) NEW_LINE print ( atleast_x ( 1 , 0 , n - 1 , 0 , n - 1 , 0 ) ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 3 , 2 , 4 , 6 ] NEW_LINE N = len ( arr ) NEW_LINE printAnswer ( arr , N ) NEW_LINE DEDENT