Calculating number of inversions in array using AVL Finger Tree

Question

Problem: Let $ A $ be an array of $ n $ different elements from an ordered interval.
Let $ I(A) $ be the number of inversions in array $A$, meaning, the number of pairs of indexes $ 0 \leq i < j <n $ for which it occurs that $ A[i] > A[j] $. Notice that $ 0 \leq I(A) \leq {n \choose{} 2} $ and that $ I(A) = 0 $ if and only if $ A $ is sorted.
Prove that given array $A$, it is possible to calculate $ I(A) $ in time $ O(n \log n) $.

Official answer to problem: Put the elements one by one into an AVL Finger Tree with a pointer to minimal key in the tree. After each insertion calculate $ n - TreeRank(x) $ , where $ n $ is the current number of elements after insertion and $ x $ is the node we inserted. Return the sum of these numbers.

Note: $ TreeRank(x) $ = position of $ x $ in sorted order in $ A $ ( count starts from 1 and not 0 , for example if $ A = [ 6, 5 ,8 ] $ and $ N_b , N_a $ are nodes whose keys are 6 and 5 respectively then $ TreeRank(N_b) = 2 , TreeRank(N_a) = 1 $ ).

My question: I don't understand why calculating $ n - TreeRank(x) $ each time we insert $ x $ and then summing this result, will end up giving me the total number of inversions as we put each element of the array into the tree. What's the reasoning behind this technique that it works? Can you please help to elucidate this?

Thanks in advance for any help!

Answer 1

I think there is something wrong with the definition of $TreeRank(x)$. Shouldn't it be define as the position of $x$ among the inserted items in the tree and not $A$ entirely? Otherwise, it will not work with your example.

If you use my definition, $n - TreeRank(x) $ means you are counting how many elements greater than $x$ was inserted before $x$ in the tree. That should give you the idea why you get the number of inversions.

You can compute the $TreeRank$ while you insert the element if you save the size of each subtree. Since you're using a balanced BST, the cost of computing $n - TreeRank(x) $ for each $x$ takes $O(\log n) $, hence $O(n \log n) $ in total.