基于树状数组的逆序数计算方法

周 娟，曹义亲，谢 昕

（华东交通大学1.软件学院；2.信息学院，江西南昌 330013）

n个数的置换a[1]，a[2]，…，a[n]也称为排列或数组[1-2]，若i＜j且a[i]＞a[j]，则称（a[i]，a[j]）是一个逆序对。置换中的逆序对的个数称为置换的逆序数[1，3]。逆序数是奇数的置换叫奇置换，否则叫偶置换。逆序数一般分成n个部分进行计算。令t[i]表示逆序对（a[j]，i）的个数，即排在i的左边且比i大的数的个数，则逆序数为t[1]+t[2]+…+t[n]。文[4]中利用轮换和归并排序计算奇偶性。一般来说，t[i]的计算方法是：设置1个全0的排列c[1]，c[2]，…，c[n]，对大于i的数a[j]，将c[j]置为1，设i在位置p，计算位置p左边1的个数就是t[i]，然后置c[p]＝1，下一步计算t[i-1]。

例1 设n=8，a={3，2，1，5，8，4，6，7}，则t[1]=2，t[2]=1，t[3]=0，t[4]=2，t[5]=0，t[6]=t[7]=1，t[8]=0。上述方法的时间复杂度是n2。本文提出一种复杂度为nlog2n的计算逆序数的算法，采用树状数组[5]。

1 树状数组

定义1设i整除2k，i不能整除2k+1，k为非负整数，则称2k是i的最小比特，记为lowbit（i）。

例28的最小比特是8，6的最小比特是2。把i化为2进制数后，最后的连续的0的个数就是k。奇数的最小比特是1，若i=2k，则i的最小比特就是i。

定义2设c[1]，c[2]，…，c[n]是一个数组，c[i]称为点或数。定义c[i]的父节点是c[i+lowbit（i）]。称c为树状数组。

性质1若i是奇数，则c[i]没有子节点。以c[i]为根的子树只有1个点。

性质2若i的最小比特是2k，则以c[i]为根的子树有2k个点，有k个子节点，它的k个子节点是（若i的二进制数是***100000，以k=5为例）：

例3 c[8]为根的子树有8个点，c[8]的子节点是c[4]，c[6]，c[7]。c[4]的子节点是c[2]，c[3]。c[6]的子节点是c[5]。如表1和图1所示。

表1 树状数组Tab.1 Arborescence array

图1是一颗空树，尚未放入需要计算的项目，依定义2即可得到此父子结构的一颗确定的树，据此结构特征，再通过定义c的内涵以及具体问题所引入的数组b的内涵等，即可用来解决具体计算问题。也就是说，树状数组是一个特定结构的有利工具。

由例4可以看出c[i]是b[i]与c[i]的子节点的值之和，如图2所示。

算法1计算i的最小比特2k：

2 树状数组计算逆序数

下面以例1来诠析算法4。

1）首先建立一棵空树（树状数组），如图1，这棵树共有8个位置（或称节点），每个位置上将放置数组a的一个元素，放置完毕如图3；at[a[i]]表示元素a[i]放置在at[a[i]]节点上。

2）定义4 b为节点上所放元素的个数，对于图1，b[i]=0，i=1，…，8；对于图2，b[i]=1，i=1，…，8。

3）定义数组c，c[i]为以节点i为根的树上所含元素的个数，满足式（1）。

4）定义 sum（i）为放置在i之前的节点，所含元素的个数和，可以运用算法2。

5） 首先放置最大的元素a_max，a_max=max（a[1]，…，a[n]），即n；将它放置在题设所放的位置，at[a_max]处，对于最大数的逆序数t[at[a_max]]为0，因为在它之前没有比它大的数，此时位置at[a_max]的左边也是空的，如图4中（a）第1步；再放第2大的数，如果它放在a_max之前，那么它的逆序数也为0，否则为1，如图4中（b）第2步；依次放置，某个数x放置在at[x]处，此时求x的逆序数t[at[x]]，即为求在at[x]位置的左下方和下方一个有多少个数已经放置了，即为sum（at[x]）；每放置一个元素，就以plus来更新c，计算过程和树状数组的维护过程如表2和图4。

表2 例1的计算过程Tab.2 Calculation process for example 1

3 总结

树状数组是一个查询和修改复杂度都为log（n）的数据结构，并支持随时修改某个元素的值，复杂度也为log（n）。它可以很高效地进行区间统计。在思想上类似于线段树[8-10]，比线段树节省空间，编程复杂度比线段树低，但适用范围比线段树小。总之树状数组有着简单易用的特点，容易记忆。

[1]RICHARDABRUALDI.组合数学[M].5版.北京：机械工业出版社，2009：54-55.

[2]王延明.关于排列逆序数的进一步性质及其应用[J].枣庄学院学报，2007，24（5）：12-13.

[3]张翠，张英瑞.关于逆序数相同的n级排列个数的讨论[J].洛阳师范学院学报，2010，29（5）：24-25.

[4]周尚超.置换奇偶性的快速算法[J].华东交通大学学报，2007，24（1）：87-89.

[5]刘洋.基于纹理合成的图像修复与基于分形的图像分割方法的研究与应用[D].吉林：吉林大学，2010：71-73.

[6]谭浩强.C程序设计教程[M].北京：清华大学出版社，2007：33.

[7]钱能.C++程序设计教程[M].2版.北京：清华大学出版社，2005：119-122.

[8]林盛华.线段树在程序设计中的应用[J].大众科技，2005（4）：68-69.

[9]李博涵，郝忠孝.近似查询中重叠区域的扫描计算[J]，计算机工程，2008，34（13）:10-12.

[10]CHANG YEIN，WU CHENCHANG，SHEN JUNHONG，et al.Range queries based on a structured segment tree in p2p systems[C]//Proceedings of the 2010 17th IEEE International Conference and Workshops on the Engineering of Computer-Based Systems，2010：91-99.