Range Minimum Query ( Square Root Decomposition and Sparse Table ) | Python3 program to do range minimum query in O ( 1 ) time with O ( n Log n ) extra space and O ( n Log n ) preprocessing time ; lookup [ i ] [ j ] is going to store index of minimum value in arr [ i . . j ] . Ideally lookup table size should not be fixed and should be determined using n Log n . It is kept constant to keep code simple . ; Structure to represent a query range ; Fills lookup array lookup [ ] [ ] in bottom up manner . ; Initialize M for the intervals with length 1 ; Compute values from smaller to bigger intervals ; Compute minimum value for all intervals with size 2 ^ j ; For arr [ 2 ] [ 10 ] , we compare arr [ lookup [ 0 ] [ 3 ] ] and arr [ lookup [ 3 ] [ 3 ] ] ; Returns minimum of arr [ L . . R ] ; For [ 2 , 10 ] , j = 3 ; For [ 2 , 10 ] , we compare arr [ lookup [ 0 ] [ 3 ] ] and arr [ lookup [ 3 ] [ 3 ] ] , ; Prints minimum of given m query ranges in arr [ 0. . n - 1 ] ; Fills table lookup [ n ] [ Log n ] ; One by one compute sum of all queries ; Left and right boundaries of current range ; Print sum of current query range ; Driver Code
from math import log2 NEW_LINE MAX = 500 NEW_LINE lookup = [ [ 0 for i in range ( 500 ) ] for j in range ( 500 ) ] 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 : list , n : int ) : NEW_LINE INDENT global lookup NEW_LINE for i in range ( n ) : NEW_LINE INDENT lookup [ i ] [ 0 ] = i NEW_LINE DEDENT j = 1 NEW_LINE while ( 1 << j ) <= n : NEW_LINE INDENT i = 0 NEW_LINE while i + ( 1 << j ) - 1 < n : NEW_LINE INDENT if ( arr [ lookup [ i ] [ j - 1 ] ] < arr [ lookup [ i + ( 1 << ( j - 1 ) ) ] [ j - 1 ] ] ) : NEW_LINE INDENT lookup [ i ] [ j ] = lookup [ i ] [ j - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT lookup [ i ] [ j ] = lookup [ i + ( 1 << ( j - 1 ) ) ] [ j - 1 ] NEW_LINE DEDENT i += 1 NEW_LINE DEDENT j += 1 NEW_LINE DEDENT DEDENT def query ( arr : list , L : int , R : int ) -> int : NEW_LINE INDENT global lookup NEW_LINE j = int ( log2 ( R - L + 1 ) ) NEW_LINE if ( arr [ lookup [ L ] [ j ] ] <= arr [ lookup [ R - ( 1 << j ) + 1 ] [ j ] ] ) : NEW_LINE INDENT return arr [ lookup [ L ] [ j ] ] NEW_LINE DEDENT else : NEW_LINE INDENT return arr [ lookup [ R - ( 1 << j ) + 1 ] [ j ] ] NEW_LINE DEDENT DEDENT def RMQ ( arr : list , n : int , q : list , m : int ) : 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 ▁ [ % d , ▁ % d ] ▁ is ▁ % d " % ( L , R , query ( arr , 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