Sparse Table | Python3 program to do range minimum query using sparse table ; 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 ] [ 7 ] ] and arr [ lookup [ 3 ] [ 10 ] ] ; Returns minimum of arr [ L . . R ] ; Find highest power of 2 that is smaller than or equal to count of elements in given range . For [ 2 , 10 ] , j = 3 ; Compute minimum of last 2 ^ j elements with first 2 ^ j elements in range . For [ 2 , 10 ] , we compare arr [ lookup [ 0 ] [ 3 ] ] and arr [ lookup [ 3 ] [ 3 ] ] , ; Driver Code
import math NEW_LINE def buildSparseTable ( arr , n ) : NEW_LINE INDENT for i in range ( 0 , n ) : NEW_LINE INDENT lookup [ i ] [ 0 ] = arr [ 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 ( lookup [ i ] [ j - 1 ] < 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 ( L , R ) : NEW_LINE INDENT j = int ( math . log2 ( R - L + 1 ) ) NEW_LINE if lookup [ L ] [ j ] <= lookup [ R - ( 1 << j ) + 1 ] [ j ] : NEW_LINE INDENT return lookup [ L ] [ j ] NEW_LINE DEDENT else : NEW_LINE INDENT return lookup [ R - ( 1 << j ) + 1 ] [ j ] 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 MAX = 500 NEW_LINE lookup = [ [ 0 for i in range ( MAX ) ] for j in range ( MAX ) ] NEW_LINE buildSparseTable ( a , n ) NEW_LINE print ( query ( 0 , 4 ) ) NEW_LINE print ( query ( 4 , 7 ) ) NEW_LINE print ( query ( 7 , 8 ) ) NEW_LINE DEDENT