Queries for elements greater than K in the given index range using Segment Tree | C ++ implementation of the approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > merge ( vector < int > & v1 , vector < int > & v2 ) { int i = 0 , j = 0 ; vector < int > v ; while ( i < v1 . size ( ) && j < v2 . size ( ) ) { if ( v1 [ i ] <= v2 [ j ] ) { v . push_back ( v1 [ i ] ) ; i ++ ; } else { v . push_back ( v2 [ j ] ) ; j ++ ; } } for ( int k = i ; k < v1 . size ( ) ; k ++ ) v . push_back ( v1 [ k ] ) ; for ( int k = j ; k < v2 . size ( ) ; k ++ ) v . push_back ( v2 [ k ] ) ; return v ; } void buildTree ( vector < int > * tree , int * arr , int index , int s , int e ) { if ( s == e ) { tree [ index ] . push_back ( arr [ s ] ) ; return ; } int mid = ( 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 ] ) ; } int query ( vector < int > * tree , int index , int s , int e , int l , int r , int k ) { if ( r < s l > e ) return 0 ; if ( s >= l && e <= r ) { return ( tree [ index ] . size ( ) - ( lower_bound ( tree [ index ] . begin ( ) , tree [ index ] . end ( ) , k ) - tree [ index ] . begin ( ) ) ) ; } int mid = ( s + e ) / 2 ; return ( query ( tree , 2 * index , s , mid , l , r , k ) + query ( tree , 2 * index + 1 , mid + 1 , e , l , r , k ) ) ; } void performQueries ( int L [ ] , int R [ ] , int K [ ] , int n , int q , vector < int > tree [ ] ) { for ( int i = 0 ; i < q ; i ++ ) { cout << query ( tree , 1 , 0 , n - 1 , L [ i ] - 1 , R [ i ] - 1 , K [ i ] ) << endl ; } } int main ( ) { int arr [ ] = { 7 , 3 , 9 , 13 , 5 , 4 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; vector < int > tree [ 4 * n + 1 ] ; buildTree ( tree , arr , 1 , 0 , n - 1 ) ; int L [ ] = { 1 , 2 } ; int R [ ] = { 4 , 6 } ; int K [ ] = { 6 , 8 } ; int q = sizeof ( L ) / sizeof ( L [ 0 ] ) ; performQueries ( L , R , K , n , q , tree ) ; return 0 ; }