we can use self balancing BST for this problem to yield the complexity O(nlogn) ..where every node will contain the sum of the node values on it left sub tree .. you can check this post..its pretty similar (Method 2)
http://www.geeksforgeeks.org/archives/17235 On Mon, Mar 12, 2012 at 12:58 AM, Piyush Kapoor <pkjee2...@gmail.com> wrote: > This can be done very easily with the help of a Binary Indexed Tree,and it > is very short to code as well.Simply process the numbers in order,and for > each number output the cumulative frequency of the index of the number you > are processing. > > > -- > 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 > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- *Dheeraj Sharma* -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
