@Navin Naidu: you are wrong in your preprocessing it will take log(n) for insertion in red black so creating a red black it will take O(n log n) who it is O(n)....?
On Thu, Apr 1, 2010 at 1:50 PM, Navin Naidu <[email protected]> wrote: > 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]<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]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
