Queries to check whether a given digit is present in the given Range | Java 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
import java . io . * ; import java . util . * ; class GFG { static int N = 6 ; @ SuppressWarnings ( " unchecked " ) static HashSet < Integer > [ ] Tree = new HashSet [ 6 * N ] ; static { for ( int i = 0 ; i < 6 * N ; i ++ ) Tree [ i ] = new HashSet < > ( ) ; } static void buildTree ( int [ ] arr , int idx , int s , int e ) { if ( s == e ) { Tree [ idx ] . add ( arr [ s ] ) ; return ; } int mid = ( s + e ) / 2 ; buildTree ( arr , 2 * idx , s , mid ) ; buildTree ( arr , 2 * idx + 1 , mid + 1 , e ) ; for ( int it : Tree [ 2 * idx ] ) Tree [ idx ] . add ( it ) ; for ( int it : Tree [ 2 * idx + 1 ] ) Tree [ idx ] . add ( it ) ; } static boolean query ( int idx , int s , int e , int qs , int qe , int x ) { if ( qs <= s && e <= qe ) { if ( Collections . frequency ( Tree [ idx ] , x ) != 0 ) return true ; else return false ; } if ( qe < s e < qs ) return false ; int mid = ( s + e ) / 2 ; boolean LeftAns = query ( 2 * idx , s , mid , qs , qe , x ) ; boolean RightAns = query ( 2 * idx + 1 , mid + 1 , e , qs , qe , x ) ; return ( LeftAns RightAns ) ; } public static void main ( String [ ] args ) { int [ ] arr = { 1 , 3 , 3 , 9 , 8 , 7 } ; int n = arr . length ; 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 ) ) System . out . println ( " Yes " ) ; else System . out . println ( " No " ) ; l = 2 ; r = 5 ; x = 3 ; if ( query ( 1 , 0 , n - 1 , l , r , x ) ) System . out . println ( " Yes " ) ; else System . out . println ( " No " ) ; } }