It is simple.
Initialize BIT[MAXN+1] to zero.
1.Iterate from Right to left
2.For each element array[i] Check how many elements are smaller than
array[i].
This can be done by just a simple query(array[i]-1);
3. Update the array[i]th index in BIT by 1.
// Simple code snippet.
long ans=0;
For(int i=sz-1;i>=0;i--){
ans+=query(array[i]-1);
update(array[i],1);
}
You are consider the array element as indices of BIT so make sure u have
mapped all the elements of the array from 1 to MAXN which can be done by
sorting the input and using c++ stl maps.
--
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.
