Range LCM Queries | LCM of given range queries using Segment Tree ; allocate space for tree ; declaring the array globally ; Function to return gcd of a and b ; utility function to find lcm ; Function to build the segment tree Node starts beginning index of current subtree . start and end are indexes in arr [ ] which is global ; If there is only one element in current subarray ; build left and right segments ; build the parent ; Function to make queries for array range ) l , r ) . Node is index of root of current segment in segment tree ( Note that indexes in segment tree begin with 1f or simplicity ) . start and end are indexes of subarray covered by root of current segment . ; Completely outside the segment , returning 1 will not affect the lcm ; ; completely inside the segment ; partially inside ; Driver Code ; initialize the array ; build the segment tree ; Now we can answer each query efficiently Print LCM of ( 2 , 5 ) ; Print LCM of ( 5 , 10 ) ; Print LCM of ( 0 , 10 )
MAX = 1000 NEW_LINE tree = [ 0 ] * ( 4 * MAX ) NEW_LINE arr = [ 0 ] * MAX NEW_LINE def gcd ( a : int , b : int ) : NEW_LINE INDENT if a == 0 : NEW_LINE INDENT return b NEW_LINE DEDENT return gcd ( b % a , a ) NEW_LINE DEDENT def lcm ( a : int , b : int ) : NEW_LINE INDENT return ( a * b ) // gcd ( a , b ) NEW_LINE DEDENT def build ( node : int , start : int , end : int ) : NEW_LINE INDENT if start == end : NEW_LINE INDENT tree [ node ] = arr [ start ] NEW_LINE return NEW_LINE DEDENT mid = ( start + end ) // 2 NEW_LINE build ( 2 * node , start , mid ) NEW_LINE build ( 2 * node + 1 , mid + 1 , end ) NEW_LINE left_lcm = tree [ 2 * node ] NEW_LINE right_lcm = tree [ 2 * node + 1 ] NEW_LINE tree [ node ] = lcm ( left_lcm , right_lcm ) NEW_LINE DEDENT def query ( node : int , start : int , end : int , l : int , r : int ) : NEW_LINE INDENT if end < l or start > r : NEW_LINE INDENT return 1 NEW_LINE DEDENT if l <= start and r >= end : NEW_LINE INDENT return tree [ node ] NEW_LINE DEDENT mid = ( start + end ) // 2 NEW_LINE left_lcm = query ( 2 * node , start , mid , l , r ) NEW_LINE right_lcm = query ( 2 * node + 1 , mid + 1 , end , l , r ) NEW_LINE return lcm ( left_lcm , right_lcm ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr [ 0 ] = 5 NEW_LINE arr [ 1 ] = 7 NEW_LINE arr [ 2 ] = 5 NEW_LINE arr [ 3 ] = 2 NEW_LINE arr [ 4 ] = 10 NEW_LINE arr [ 5 ] = 12 NEW_LINE arr [ 6 ] = 11 NEW_LINE arr [ 7 ] = 17 NEW_LINE arr [ 8 ] = 14 NEW_LINE arr [ 9 ] = 1 NEW_LINE arr [ 10 ] = 44 NEW_LINE build ( 1 , 0 , 10 ) NEW_LINE print ( query ( 1 , 0 , 10 , 2 , 5 ) ) NEW_LINE print ( query ( 1 , 0 , 10 , 5 , 10 ) ) NEW_LINE print ( query ( 1 , 0 , 10 , 0 , 10 ) ) NEW_LINE DEDENT