Queries for elements greater than K in the given index range using Segment Tree | C ++ implementation of the approach ; combine function to make parent node ; building the tree ; leaf node ; merging the nodes while backtracking . ; performing query ; Out of Bounds ; completely overlaps ; partially overlaps ; Driver Code ; 1 - based indexing
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > arr ( 1000000 ) , tree ( 4 * arr . size ( ) ) ; int combine ( int a , int b ) { if ( a != 0 && b != 0 ) { return a ; } if ( a >= b ) { return a ; } return b ; } void buildTree ( int ind , int low , int high , int x ) { if ( low == high ) { if ( arr [ low ] > x ) { tree [ ind ] = arr [ low ] ; } else { tree [ ind ] = 0 ; } return ; } int mid = ( low + high ) / 2 ; buildTree ( 2 * ind + 1 , low , mid , x ) ; buildTree ( 2 * ind + 2 , mid + 1 , high , x ) ; tree [ ind ] = combine ( tree [ 2 * ind + 1 ] , tree [ 2 * ind + 2 ] ) ; } int query ( int ind , int low , int high , int l , int r ) { int mid = ( low + high ) / 2 ; if ( low > r high < l ) { return 0 ; } if ( l <= low && r >= high ) { return tree [ ind ] ; } return combine ( query ( 2 * ind + 1 , low , mid , l , r ) , query ( 2 * ind + 2 , mid + 1 , high , l , r ) ) ; } int main ( ) { arr = { 7 , 3 , 9 , 13 , 5 , 4 } ; int n = 6 ; int k = 6 ; int l = 1 , r = 4 ; buildTree ( 0 , 0 , n - 1 , k ) ; cout << query ( 0 , 0 , n - 1 , l - 1 , r - 1 ) ; return 0 ; }