Queries for elements greater than K in the given index range using Segment Tree | Merge procedure to merge two vectors into a single vector ; Final vector to return after merging ; Loop continues until it reaches the end of one of the vectors ; Here , simply add the remaining elements to the vector v ; Procedure to build the segment tree ; Reached the leaf node of the segment tree ; Recursively call the buildTree on both the nodes of the tree ; Storing the final vector after merging the two of its sorted child vector ; Query procedure to get the answer for each query l and r are query range ; out of bound or no overlap ; Complete overlap Query range completely lies in the segment tree node range ; binary search to find index of k ; Partially overlap Query range partially lies in the segment tree node range ; Function to perform the queries ; Driver code ; 1 - based indexing ; Number of queries
function merge ( v1 , v2 ) { let i = 0 , j = 0 ; let v = new Array ( ) ; while ( i < v1 . length && j < v2 . length ) { if ( v1 [ i ] <= v2 [ j ] ) { v . push ( v1 [ i ] ) ; i ++ ; } else { v . push ( v2 [ j ] ) ; j ++ ; } } for ( let k = i ; k < v1 . length ; k ++ ) v . push ( v1 [ k ] ) ; for ( let k = j ; k < v2 . length ; k ++ ) v . push ( v2 [ k ] ) ; return v ; } function buildTree ( tree , arr , index , s , e ) { if ( s == e ) { tree [ index ] . push ( arr [ s ] ) ; return ; } let mid = Math . floor ( ( s + e ) / 2 ) ; buildTree ( tree , arr , 2 * index , s , mid ) ; buildTree ( tree , arr , 2 * index + 1 , mid + 1 , e ) ; tree [ index ] = merge ( tree [ 2 * index ] , tree [ 2 * index + 1 ] ) ; } function query ( tree , index , s , e , l , r , k ) { if ( r < s l > e ) return 0 ; if ( s >= l && e <= r ) { return ( tree [ index ] . length - ( lowerBound ( tree [ index ] , tree [ index ] . length , k ) ) ) ; } let mid = Math . floor ( ( s + e ) / 2 ) ; return ( query ( tree , 2 * index , s , mid , l , r , k ) + query ( tree , 2 * index + 1 , mid + 1 , e , l , r , k ) ) ; } function lowerBound ( array , length , value ) { let low = 0 ; let high = length ; while ( low < high ) { let mid = Math . floor ( ( low + high ) / 2 ) ; if ( value <= array [ mid ] ) { high = mid ; } else { low = mid + 1 ; } } return low ; } function performQueries ( L , R , K , n , q , tree ) { for ( let i = 0 ; i < q ; i ++ ) { document . write ( query ( tree , 1 , 0 , n - 1 , L [ i ] - 1 , R [ i ] - 1 , K [ i ] ) + " " ) ; } } let arr = [ 7 , 3 , 9 , 13 , 5 , 4 ] ; let n = arr . length ; let tree = new Array ( ) ; for ( let i = 0 ; i < 4 * n + 1 ; i ++ ) { tree . push ( [ ] ) } buildTree ( tree , arr , 1 , 0 , n - 1 ) ; let L = [ 1 , 2 ] ; let R = [ 4 , 6 ] ; let K = [ 6 , 8 ] ; let q = L . length ; performQueries ( L , R , K , n , q , tree ) ;