TAOCP 5.1.1 Exercise 3
Let $p_i$ denote the position of the element $i$ in the permutation, so that $a_{p_i}=i$.
Exercise 3. [**] [26] Design an algorithm that computes the inversion table $b_1 b_2 \dots b_n$ corresponding to a given permutation $a_1 a_2 \dots a_n$ of ${1,2,\dots,n}$, where the running time is essentially proportional to $n \log n$ on typical computers.
Verified: no
Solve time: 35m40s
Let $p_i$ denote the position of the element $i$ in the permutation, so that $a_{p_i}=i$. By definition, $b_i$ is the number of elements greater than $i$ that occur to the left of $i$, hence
$$ b_i=#{,j>i : p_j<p_i,}. $$
Thus the problem is to maintain a dynamic set of positions and, for each $i=n,n-1,\ldots,1$, determine how many previously inserted positions lie to the left of $p_i$.
Store the positions $p_1,p_2,\ldots,p_n$ in an array obtained by scanning the permutation once. Then maintain the set of positions already processed by means of a balanced binary search tree whose nodes contain subtree sizes. Process the values in the order $n,n-1,\ldots,1$. When position $p_i$ is inserted, the tree can determine in $O(\log n)$ time how many stored positions are less than $p_i$; this number is exactly $b_i$. After computing $b_i$, insert $p_i$ into the tree and continue.
The preliminary construction of the array $p$ requires $O(n)$ time. Each of the $n$ rank queries and insertions requires $O(\log n)$ time. Therefore the total running time is
$$ O(n)+n,O(\log n)=O(n\log n), $$
which is essentially proportional to $n\log n$ on typical computers.