How do we know INVERSIONS-COUNT algorithm implemented in balanced tree really works?

Question

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?

Answer 1

At step $i$, the rank of $L[i]$ in $T$ is the number of elements in $L[i],\ldots,L[|L|-1]$ which are at most $L[i]$. Taking into account the $-|L|$ in the beginning, we see that the algorithm counts the number of pairs $i<j$ such that $L[j] \leq L[i]$, which is exactly the number of inversions (assuming all elements are distinct).