Queries to check whether a given digit is present in the given Range | Python3 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
N = 6 NEW_LINE Tree = [ 0 ] * ( 6 * N ) NEW_LINE for i in range ( 6 * N ) : NEW_LINE INDENT Tree [ i ] = set ( ) NEW_LINE DEDENT def buildTree ( arr : list , idx : int , s : int , e : int ) -> None : NEW_LINE INDENT global Tree NEW_LINE if s == e : NEW_LINE INDENT Tree [ idx ] . add ( arr [ s ] ) NEW_LINE return NEW_LINE DEDENT mid = ( s + e ) // 2 NEW_LINE buildTree ( arr , 2 * idx , s , mid ) NEW_LINE buildTree ( arr , 2 * idx + 1 , mid + 1 , e ) NEW_LINE for it in Tree [ 2 * idx ] : NEW_LINE INDENT Tree [ idx ] . add ( it ) NEW_LINE DEDENT for it in Tree [ 2 * idx + 1 ] : NEW_LINE INDENT Tree [ idx ] . add ( it ) NEW_LINE DEDENT DEDENT def query ( idx : int , s : int , e : int , qs : int , qe : int , x : int ) -> bool : NEW_LINE INDENT global Tree NEW_LINE if qs <= s and e <= qe : NEW_LINE INDENT if list ( Tree [ idx ] ) . count ( x ) != 0 : NEW_LINE INDENT return True NEW_LINE DEDENT else : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT if qe < s or e < qs : NEW_LINE INDENT return False NEW_LINE DEDENT mid = ( s + e ) // 2 NEW_LINE leftAns = query ( 2 * idx , s , mid , qs , qe , x ) NEW_LINE rightAns = query ( 2 * idx + 1 , mid + 1 , e , qs , qe , x ) NEW_LINE return ( leftAns or rightAns ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , 3 , 3 , 9 , 8 , 7 ] NEW_LINE n = len ( arr ) NEW_LINE buildTree ( arr , 1 , 0 , n - 1 ) NEW_LINE l = 0 NEW_LINE r = 3 NEW_LINE x = 2 NEW_LINE if query ( 1 , 0 , n - 1 , l , r , x ) : NEW_LINE INDENT print ( " YES " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " NO " ) NEW_LINE DEDENT l = 2 NEW_LINE r = 5 NEW_LINE x = 3 NEW_LINE if query ( 1 , 0 , n - 1 , l , r , x ) : NEW_LINE INDENT print ( " YES " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " NO " ) NEW_LINE DEDENT DEDENT