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 readonly 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
using System ; using System . Collections . Generic ; class GFG { static List < int > merge ( List < int > v1 , List < int > v2 ) { int i = 0 , j = 0 ; List < int > v = new List < int > ( ) ; while ( i < v1 . Count && j < v2 . Count ) { if ( v1 [ i ] <= v2 [ j ] ) { v . Add ( v1 [ i ] ) ; i ++ ; } else { v . Add ( v2 [ j ] ) ; j ++ ; } } for ( int k = i ; k < v1 . Count ; k ++ ) v . Add ( v1 [ k ] ) ; for ( int k = j ; k < v2 . Count ; k ++ ) v . Add ( v2 [ k ] ) ; return v ; } static void buildTree ( List < int > [ ] tree , int [ ] arr , int index , int s , int e ) { if ( s == e ) { tree [ index ] . Add ( 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 ] ) ; } static int query ( List < 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 ] . Count - lowerBound ( tree [ index ] , tree [ index ] . Count , k ) ) ; } 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 ) ) ; } static void performQueries ( int [ ] L , int [ ] R , int [ ] K , int n , int q , List < int > [ ] tree ) { for ( int i = 0 ; i < q ; i ++ ) { Console . WriteLine ( query ( tree , 1 , 0 , n - 1 , L [ i ] - 1 , R [ i ] - 1 , K [ i ] ) ) ; } } static int lowerBound ( List < int > array , int length , int value ) { int low = 0 ; int high = length ; while ( low < high ) { int mid = ( low + high ) / 2 ; if ( value <= array [ mid ] ) { high = mid ; } else { low = mid + 1 ; } } return low ; } public static void Main ( String [ ] args ) { int [ ] arr = { 7 , 3 , 9 , 13 , 5 , 4 } ; int n = arr . Length ; List < int > [ ] tree = new List < int > [ 4 * n + 1 ] ; for ( int i = 0 ; i < ( 4 * n + 1 ) ; i ++ ) { tree [ i ] = new List < int > ( ) ; } buildTree ( tree , arr , 1 , 0 , n - 1 ) ; int [ ] L = { 1 , 2 } ; int [ ] R = { 4 , 6 } ; int [ ] K = { 6 , 8 } ; int q = L . Length ; performQueries ( L , R , K , n , q , tree ) ; } }