text: Sparse Table | Python3 program to do range minimum query using sparse table ; Fills lookup array lookup [ ] [ ] in bottom up manner . ; GCD of single element is element itself ; Build sparse table ; 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 GCD of last 2 ^ j elements with first 2 ^ j elements in range . For [ 2 , 10 ] , we find GCD of arr [ lookup [ 0 ] [ 3 ] ] and arr [ lookup [ 3 ] [ 3 ] ] , ; Driver Code
code: import math NEW_LINE def buildSparseTable ( arr , n ) : NEW_LINE INDENT for i in range ( 0 , n ) : NEW_LINE INDENT table [ i ] [ 0 ] = arr [ i ] NEW_LINE DEDENT j = 1 NEW_LINE while ( 1 << j ) <= n : NEW_LINE INDENT i = 0 NEW_LINE while i <= n - ( 1 << j ) : NEW_LINE INDENT table [ i ] [ j ] = math . gcd ( table [ i ] [ j - 1 ] , table [ i + ( 1 << ( j - 1 ) ) ] [ j - 1 ] ) NEW_LINE 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 return math . gcd ( table [ L ] [ j ] , table [ R - ( 1 << j ) + 1 ] [ j ] ) NEW_LINE 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 table = [ [ 0 for i in range ( MAX ) ] for j in range ( MAX ) ] NEW_LINE buildSparseTable ( a , n ) NEW_LINE print ( query ( 0 , 2 ) ) NEW_LINE print ( query ( 1 , 3 ) ) NEW_LINE print ( query ( 4 , 5 ) ) NEW_LINE DEDENT