Queries to check whether a given digit is present in the given Range | CPP program to answer Queries to check whether a given digit is present in the given range ; Segment Tree with set at each node ; Funtiom to build the segment tree ; Left child node ; Right child node ; Merging child nodes to get parent node . Since set is used , it will remove redundant digits . ; Function to query a range ; Complete Overlapp condition return true if digit is present . else false . ; No Overlapp condition Return false ; If digit is found in any child return true , else False ; Driver Code ; Build the tree ; Query 1 ; Query 2
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  6 NEW_LINE set < int > Tree [ 6 * N ] ; void buildTree ( int * arr , int idx , int s , int e ) { if ( s == e ) { Tree [ idx ] . insert ( arr [ s ] ) ; return ; } int mid = ( s + e ) >> 1 ; buildTree ( arr , 2 * idx , s , mid ) ; buildTree ( arr , 2 * idx + 1 , mid + 1 , e ) ; for ( auto it : Tree [ 2 * idx ] ) { Tree [ idx ] . insert ( it ) ; } for ( auto it : Tree [ 2 * idx + 1 ] ) { Tree [ idx ] . insert ( it ) ; } } bool query ( int idx , int s , int e , int qs , int qe , int x ) { if ( qs <= s && e <= qe ) { if ( Tree [ idx ] . count ( x ) != 0 ) { return true ; } else return false ; } if ( qe < s e < qs ) { return false ; } int mid = ( s + e ) >> 1 ; bool LeftAns = query ( 2 * idx , s , mid , qs , qe , x ) ; bool RightAns = query ( 2 * idx + 1 , mid + 1 , e , qs , qe , x ) ; return LeftAns or RightAns ; } int main ( ) { int arr [ ] = { 1 , 3 , 3 , 9 , 8 , 7 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; buildTree ( arr , 1 , 0 , n - 1 ) ; int l , r , x ; l = 0 , r = 3 , x = 2 ; if ( query ( 1 , 0 , n - 1 , l , r , x ) ) cout << " YES " << ' ' ; else cout << " NO " << ' ' ; l = 2 , r = 5 , x = 3 ; if ( query ( 1 , 0 , n - 1 , l , r , x ) ) cout << " YES " << ' ' ; else cout << " NO " << ' ' ; return 0 ; }