Cartesian trees could also help.
Cartesian tree takes O(n) time to build, and if you have the count of how
many nodes are there in a tree rooted at any node, by just having the index
of the element also stored there. Once the cartesian tree is built, just
traverse from the root and find how many nodes are there in the left subtree
from its left child node, and that is the number of inversions for the root
node. Keep doing this for all emenents and kep adding them to a counter.
When you have gone through all the n nodes, you have the total numbr of
inversions, that traversal would also take O(n) time.
When you are at any node, and you know its index in the array, all the
elements to the left sub-tree are inversions because all the elements to the
left of the node are to the left of in the actual array, and that this node
now holds all of the left side of the array rooted at its left child, so all
of them are inversions. And they are the only inversions possible for the
node in questions.
Let me know your views.
Regards
Topo.
On Thu, May 12, 2011 at 5:16 PM, Akshata Sharma
<akshatasharm...@gmail.com>wrote:
> @Anshu:
> My logic:
> during merge step, lets say you have two array left and right (both are
> sorted) and you are going to merge it.
>
> l[i] represent the element of left arrray
> r[j] represent the element of right array
>
> if (r[j] < l[i]) {
> increase the inversion count by the number of elements lefts in left
> array
> put element r[j] into merged array
> j++
> } else {
> no increase in count, just put the element r[i] into merged array
> i++;
>
> This will be O(nlogn) solution. Can we do better using BIT or segment
> trees? Can you please provide me some hint of how to solve it using segment
> trees, I just know the basics of it..
>
> On Thu, May 12, 2011 at 5:00 PM, anshu mishra
> <anshumishra6...@gmail.com>wrote:
>
>> explain your logic instead of posting code, use binary index tree or
>> segment tree or bst to solve this problem.
>>
>> --
>> 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.
>>
>
> --
> 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.
>
--
Topo.
There are days when solitude is a heady wine that intoxicates you with
freedom, others when it is a bitter tonic, and still others when it is a
poison that makes you beat your head against the wall. ~Colette
--
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.
