周 娟，曹义亲，谢 昕

（华东交通大学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的内涵等，即可用来解决具体计算问题。……