计算排列反演表的\(n log( n)\)算法

此题是TAOCP中的5.1.1 Exercise 26
Design an algorithm that computes the inversion table \(b_1 b_2 ... b_n\) corresponding to a given permutation \(a_1 a_2 ... a_n\) of {1,2,3..,n}, where the running time is essentially proportional to \(n log (n)\) on typical computers

书后给出的答案可能需要多读几遍才能理解
基本思路是，按二进制位考察每一个\(a_i\)，从最高位开始，比如计算1到9的排列，则将所有数先分成两组，1，2，……，7为一组，8和9为一组，然后计算不同组数之间的前后关系。同组之间的前后则暂时先不计算。

第二遍，将所有数分成两类，每一类中又分两组，第一类有1，2，3和4，5，6，7两组，第二类有8，9两个数。计算同一类中两组的先后关系，也就是说，4，5，6，7之间的先后暂不计算，但算这4个数和1，2，3之间的先后关系。

第三遍，继续细分成4类 第一类有 两组 1，和2，3, 第二类有4，5，和6，7.第三类有8，9一组
再一遍计算同一类中两组的先后关系。

最后一遍，所有数两两分类：{1},{2,3}{4,5}{6,7}{8,9}每一类中有两个数，计算这两个数的先后关系。

将此4遍的结果加起来，就是最后的结果。


另外其实此题有更直观的解法
先建立空集S, 对排列依次做，取出排列的第i个元素\(a_i\)
求得S中比\(a_i\)大的元素个数\(（rank(a_i)\), 令\({b_a}_i=rank(a_i)\)
将\(a_i\)放入S中

于是问题就转化为，是否有数据结构可以在\(log(n)\)的时间内做到插入和计算rank的操作，这是可能的，只需要简单修改平衡二叉树，例如AVL树，在每个节点保存左右子树的节点数即可。因为AVL的插入和查找都是\(log( n)\)级别的操作。而加上左右子树节点数后，查找操作可以得出当前树中比目标数大的个数的值。