How do we know INVERSIONS-COUNT algorithm (exercise 14.1-7 from here), implemented in balanced tree really works?
We assume that the tree data structure we're using is an order statistic tree which means that a) it's a balanced binary tree, b) each node $x$ is augmented with $size$ field which tells us the size of the node's subtree (its inner nodes, including $x$).
We also have an array $L[1..n]$ which contains the values of the keys of the tree (not necessarily sorted).
The algorithm uses two helper functions:
RANK(Tree, node_x) - returns the rank of the key of
node_x in array $L$.
SEARCH(Tree, L[i]) - returns the node with the same key as the element $L[i]$ in the given array.
This is the code:
Construct an order statistic tree T for all the elements in L t = −|L| for i from 0 to |L| − 1 do t = t + RANK(T, SEARCH(T, L[i])) remove the node corresponding to L[i] from T end for return t
If the array is sorted then there're no inversions. Therefore
t is incremented each time by $1$ because in sorted array each new element is the minimal one and has rank $1$ (because we delete the last node).
If the array is not sorted then why are we guaranteed that the ranks will at some point "overtake"
t and produce the correct amount of inversions?