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 function to check the above program 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 )
const MAX = 1000 var tree = new Array ( 4 * MAX ) ; var arr = new Array ( MAX ) ; function gcd ( a , b ) { if ( a == 0 ) return b ; return gcd ( b % a , a ) ; } function lcm ( a , b ) { return Math . floor ( a * b / gcd ( a , b ) ) ; } function build ( node , start , end ) { if ( start == end ) { tree [ node ] = arr [ start ] ; return ; } let mid = Math . floor ( ( start + end ) / 2 ) ; build ( 2 * node , start , mid ) ; build ( 2 * node + 1 , mid + 1 , end ) ; let left_lcm = tree [ 2 * node ] ; let right_lcm = tree [ 2 * node + 1 ] ; tree [ node ] = lcm ( left_lcm , right_lcm ) ; } function query ( node , start , end , l , r ) { if ( end < l start > r ) return 1 ; if ( l <= start && r >= end ) return tree [ node ] ; let mid = Math . floor ( ( start + end ) / 2 ) ; let left_lcm = query ( 2 * node , start , mid , l , r ) ; let right_lcm = query ( 2 * node + 1 , mid + 1 , end , l , r ) ; return lcm ( left_lcm , right_lcm ) ; } arr [ 0 ] = 5 ; arr [ 1 ] = 7 ; arr [ 2 ] = 5 ; arr [ 3 ] = 2 ; arr [ 4 ] = 10 ; arr [ 5 ] = 12 ; arr [ 6 ] = 11 ; arr [ 7 ] = 17 ; arr [ 8 ] = 14 ; arr [ 9 ] = 1 ; arr [ 10 ] = 44 ; build ( 1 , 0 , 10 ) ; document . write ( query ( 1 , 0 , 10 , 2 , 5 ) + " " ) ; document . write ( query ( 1 , 0 , 10 , 5 , 10 ) + " " ) ; document . write ( query ( 1 , 0 , 10 , 0 , 10 ) + " " ) ;