Discuss the below:
Q: Show how to use an order-statistic tree to count the number of inversions in an array of size n in time O(n lg n).
Note that we call a pair (i,j) an inversion if i < j, but key[i] > key[j]. Thus, an increasing sequence has no inversions. A decreasing list has the maximum number of inversions, n(n-1)/2.
We start by letting k be the number of inversions in the sequence. We then create an order-statistic tree and store with each node the original index in the sequence.
Is there anything else we store in the node and what would be the algorithm for the number of inversions?