I think preprocessing time of O(n) will be required to construct the data structure.
*Data Structure used:* R-B tree. * The additional data that will be stored in each node is : * a) the size of subtree at each node b) parent node. *New Query:* Find the kth element in the tree: Complexity will be O(lgn) So the total complexity to find all the values between x1 and x2 will be: complexity to find x1 + complexity to find x2 + finding all the values between these two points (this includes finding LCA) = O(lgn) + O(lgn) + O(lgn) = O(lgn) preprocessing time : O(n) complexity of query : O(lgn) On Wed, Mar 31, 2010 at 11:54 PM, BlackdiamonD <[email protected]>wrote: > *Binary Indexed Trees* or *Segment Interval trees*. building them also it > will take O(n log(n)) > ..i feel for a particular query it will be difficult less than O(n) > .because .u must know all the element. > > > On Wed, Mar 31, 2010 at 8:26 PM, Priyanka Chatterjee > <[email protected]>wrote: > >> The list of N integers is not sorted. >> The solution is asked for a particular query. >> >> @Abhijit Reddy: Can you elaborate more on* Binary Indexed Trees* or *Segment >> Interval trees*. May be you opted for the correct data structure. Please >> give the algorithm. >> >> @All: Doing a sorting for O(n logn) and then binary search for x1 and x2 >> in O(logn) will be less efficient than the simple solution of O(n). Think on >> the data structure that can optimize it. >> Is it possible in time complexity < O(n)? >> >>> >>> >> >> >> -- >> Thanks & Regards, >> Priyanka Chatterjee >> Third Year Undergraduate Student, >> Computer Science & Engineering, >> National Institute Of Technology,Durgapur >> India >> http://priyanka-nit.blogspot.com/ >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<algogeeks%[email protected]> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > ~~~~BL/\CK_D!AMOND~~~~~~~~ > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Thanks & Regards, - NMN -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
