my mistake, it will modify the structure. On Thu, Apr 1, 2010 at 1:50 PM, Navin Naidu <navinmna...@gmail.com> 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 <patidarc...@gmail.com>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 <dona.1...@gmail.com >> > 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 algoge...@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>> . >>> 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 algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > Thanks & Regards, > > - NMN > -- Thanks & Regards, - Navin Mohan Naidu Great Minds Discuss Ideas Average Minds Discuss Events Small Minds Discuss People -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
