I guess it is binary search tree. Try this and you will get what you want.
On Sep 26, 5:12 am, "mukesh agrawal" <[EMAIL PROTECTED]> wrote: > What is binary index tree ? I googled it finding irrelevent information ... > help needed .. > > On 9/25/07, Mohammad Naser Zandy <[EMAIL PROTECTED]> wrote: > > > > > > > I am agree with Sticker, > > I comes to write exactly what Sticker wrote. ;) > > It's O(N^2 / 2) that is 1+2+3+4+5+...+N. > > > On 9/25/07, Sticker <[EMAIL PROTECTED]> wrote: > > > > I saw your ideas. Some of them are correct some are not. Here is what > > > I am thinking. > > > > >From the question we know that 1 ≤ M ≤ 1000000 and 1 ≤ N ≤ 4000. So > > > notice that M >> N. Using a linked list to store M, you have to travel > > > it from either end, so at least M/2 travels each time, still larger > > > than N. So what if we keep M stored in an array(a simplest array > > > int[], called booArray) and do touch it. Rather we dynamically store > > > N? I use a linked list borLList to store all the borrowed books' > > > "original" position in booArray. > > > > Once we come across a borrowed index, we go through borLList, each > > > time a position smaller than the borrowed index, we increase the > > > borrowed index by one until we come across a position has a position > > > larger than it, then we insert this borrowed index to the current > > > position. Do another one and so on. > > > > Example: > > > 5 > > > 26 1 42 15 3 > > > 2 > > > 3 > > > 4 > > > > The booArray is 26, 1, 42, 15, 3, stored in booArray[1] to > > > booArray[5]. borLList is empty now. 3 is the first borrowed index, we > > > insert it into borLList and return booArray[3]. The next borrowed > > > index is 4, since the first element in borLList is 3, which is smaller > > > than 4, we increase this borrowed index by one, now it is 5, since no > > > larger element exists in borLList, we insert 5 into borLList and > > > return booArray[5]. Now the borLList is 3->5. > > > > As we can see, practically far less than 4000 times is required for > > > each borrowed index, which is definitely better than the double link > > > list solution (which is (S/2 -1) * (S/2 - 2) * (S/2 -3) * ... 1 as > > > given by jliang. > > > > I definitely do not agree the method to reorder the borrowed indexes. > > > This will give wrong answer. The order is important for this problem. > > > > I do not know how to use binary search tree to solve this problem, it > > > will be great if solution can be described here. > > > > On Sep 23, 12:17 pm, Jun <[EMAIL PROTECTED]> wrote: > > > > I already know how to solve it. > > > > > Binary Index Tree is good approach to solve this problem. Thanks very > > > > body involved in this discussion! > > > > > On Sep 22, 6:31 am, KK <[EMAIL PROTECTED]> wrote: > > > > > > On Sep 5, 11:07 am, jliang < [EMAIL PROTECTED]> wrote: > > > > > > > how about a doubled linked list where you can remove item at any > > > > > > index. the removing is O(1). you can also keep track of the > > > current > > > > > > removing from a doubled linked list is O(1)? How? > > > > > > > size S so if you are borrowing book at index greater than S/2, you > > > > > > traverse the list from the end, if index < S/2, you traverse from > > > the > > > > > > beginning. > > > > > > > every time a book is removed, S becomes 1 smaller, so the > > > traversal > > > > > > time is something like (S/2 -1) * (S/2 - 2) * (S/2 -3) * ... 1 > > > > > > > you can also put them in a binary tree, so every operation is > > > O(lgN) > > > > > > putting the original array in binary tree takes O(M lgM) time, and > > > you > > > > > will lose the original indices. So it's of no use. > > > > > > > so the total will be O(lgN M) > > > > > > I dont think so. correct me if I am wrong. > > -- > Mukesh Agrawal > Final Year UG CSE > IIT KGP --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
