Range Minimum Query ( Square Root Decomposition and Sparse Table ) | Python3 program to do range minimum query in O ( 1 ) time with O ( n * n ) extra space and O ( n * n ) preprocessing time . ; lookup [ i ] [ j ] is going to store index of minimum value in arr [ i . . j ] ; Structure to represent a query range ; Fills lookup array lookup [ n ] [ n ] for all possible values of query ranges ; Initialize lookup [ ] [ ] for the intervals with length 1 ; Fill rest of the entries in bottom up manner ; To find minimum of [ 0 , 4 ] , we compare minimum of arr [ lookup [ 0 ] [ 3 ] ] with arr [ 4 ] . ; Prints minimum of given m query ranges in arr [ 0. . n - 1 ] ; Fill lookup table for all possible input queries ; One by one compute sum of all queries ; Left and right boundaries of current range ; Print sum of current query range ; Driver code
MAX = 500 NEW_LINE lookup = [ [ 0 for j in range ( MAX ) ] for i in range ( MAX ) ] NEW_LINE class Query : NEW_LINE INDENT def __init__ ( self , L , R ) : NEW_LINE INDENT self . L = L NEW_LINE self . R = R NEW_LINE DEDENT DEDENT def preprocess ( arr , n ) : NEW_LINE INDENT for i in range ( n ) : NEW_LINE INDENT lookup [ i ] [ i ] = i ; NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT for j in range ( i + 1 , n ) : NEW_LINE INDENT if ( arr [ lookup [ i ] [ j - 1 ] ] < arr [ j ] ) : NEW_LINE INDENT lookup [ i ] [ j ] = lookup [ i ] [ j - 1 ] ; NEW_LINE DEDENT else : NEW_LINE INDENT lookup [ i ] [ j ] = j ; NEW_LINE DEDENT DEDENT DEDENT DEDENT def RMQ ( arr , n , q , m ) : NEW_LINE INDENT preprocess ( arr , n ) ; NEW_LINE for i in range ( m ) : NEW_LINE INDENT L = q [ i ] . L NEW_LINE R = q [ i ] . R ; NEW_LINE print ( " Minimum ▁ of ▁ [ " + str ( L ) + " , ▁ " + str ( R ) + " ] ▁ is ▁ " + str ( arr [ lookup [ L ] [ R ] ] ) ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT a = [ 7 , 2 , 3 , 0 , 5 , 10 , 3 , 12 , 18 ] NEW_LINE n = len ( a ) NEW_LINE q = [ Query ( 0 , 4 ) , Query ( 4 , 7 ) , Query ( 7 , 8 ) ] NEW_LINE m = len ( q ) NEW_LINE RMQ ( a , n , q , m ) ; NEW_LINE DEDENT