基于樹狀數(shù)組的逆序數(shù)計算方法

周 娟，曹義親，謝 昕

（華東交通大學(xué)1.軟件學(xué)院；2.信息學(xué)院，江西南昌 330013）

n個數(shù)的置換a[1]，a[2]，…，a[n]也稱為排列或數(shù)組[1-2]，若i＜j且a[i]＞a[j]，則稱（a[i]，a[j]）是一個逆序?qū)?。置換中的逆序?qū)Φ膫€數(shù)稱為置換的逆序數(shù)[1，3]。逆序數(shù)是奇數(shù)的置換叫奇置換，否則叫偶置換。逆序數(shù)一般分成n個部分進(jìn)行計算。令t[i]表示逆序?qū)Γ╝[j]，i）的個數(shù)，即排在i的左邊且比i大的數(shù)的個數(shù)，則逆序數(shù)為t[1]+t[2]+…+t[n]。文[4]中利用輪換和歸并排序計算奇偶性。一般來說，t[i]的計算方法是：設(shè)置1個全0的排列c[1]，c[2]，…，c[n]，對大于i的數(shù)a[j]，將c[j]置為1，設(shè)i在位置p，計算位置p左邊1的個數(shù)就是t[i]，然后置c[p]＝1，下一步計算t[i-1]。

例1 設(shè)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。上述方法的時間復(fù)雜度是n2。本文提出一種復(fù)雜度為nlog2n的計算逆序數(shù)的算法，采用樹狀數(shù)組[5]。

1 樹狀數(shù)組

定義1設(shè)i整除2k，i不能整除2k+1，k為非負(fù)整數(shù)，則稱2k是i的最小比特，記為lowbit（i）。

例28的最小比特是8，6的最小比特是2。把i化為2進(jìn)制數(shù)后，最后的連續(xù)的0的個數(shù)就是k。奇數(shù)的最小比特是1，若i=2k，則i的最小比特就是i。

定義2設(shè)c[1]，c[2]，…，c[n]是一個數(shù)組，c[i]稱為點或數(shù)。定義c[i]的父節(jié)點是c[i+lowbit（i）]。稱c為樹狀數(shù)組。

性質(zhì)1若i是奇數(shù)，則c[i]沒有子節(jié)點。以c[i]為根的子樹只有1個點。

性質(zhì)2若i的最小比特是2k，則以c[i]為根的子樹有2k個點，有k個子節(jié)點，它的k個子節(jié)點是（若i的二進(jìn)制數(shù)是***100000，以k=5為例）：

例3 c[8]為根的子樹有8個點，c[8]的子節(jié)點是c[4]，c[6]，c[7]。c[4]的子節(jié)點是c[2]，c[3]。c[6]的子節(jié)點是c[5]。如表1和圖1所示。

表1 樹狀數(shù)組Tab.1 Arborescence array

圖1是一顆空樹，尚未放入需要計算的項目，依定義2即可得到此父子結(jié)構(gòu)的一顆確定的樹，據(jù)此結(jié)構(gòu)特征，再通過定義c的內(nèi)涵以及具體問題所引入的數(shù)組b的內(nèi)涵等，即可用來解決具體計算問題。也就是說，樹狀數(shù)組是一個特定結(jié)構(gòu)的有利工具。

由例4可以看出c[i]是b[i]與c[i]的子節(jié)點的值之和，如圖2所示。

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

2 樹狀數(shù)組計算逆序數(shù)

下面以例1來詮析算法4。

1）首先建立一棵空樹（樹狀數(shù)組），如圖1，這棵樹共有8個位置（或稱節(jié)點），每個位置上將放置數(shù)組a的一個元素，放置完畢如圖3；at[a[i]]表示元素a[i]放置在at[a[i]]節(jié)點上。

2）定義4 b為節(jié)點上所放元素的個數(shù)，對于圖1，b[i]=0，i=1，…，8；對于圖2，b[i]=1，i=1，…，8。

3）定義數(shù)組c，c[i]為以節(jié)點i為根的樹上所含元素的個數(shù)，滿足式（1）。

4）定義 sum（i）為放置在i之前的節(jié)點，所含元素的個數(shù)和，可以運用算法2。

5） 首先放置最大的元素a_max，a_max=max（a[1]，…，a[n]），即n；將它放置在題設(shè)所放的位置，at[a_max]處，對于最大數(shù)的逆序數(shù)t[at[a_max]]為0，因為在它之前沒有比它大的數(shù)，此時位置at[a_max]的左邊也是空的，如圖4中（a）第1步；再放第2大的數(shù)，如果它放在a_max之前，那么它的逆序數(shù)也為0，否則為1，如圖4中（b）第2步；依次放置，某個數(shù)x放置在at[x]處，此時求x的逆序數(shù)t[at[x]]，即為求在at[x]位置的左下方和下方一個有多少個數(shù)已經(jīng)放置了，即為sum（at[x]）；每放置一個元素，就以plus來更新c，計算過程和樹狀數(shù)組的維護(hù)過程如表2和圖4。

表2 例1的計算過程Tab.2 Calculation process for example 1

3 總結(jié)

樹狀數(shù)組是一個查詢和修改復(fù)雜度都為log（n）的數(shù)據(jù)結(jié)構(gòu)，并支持隨時修改某個元素的值，復(fù)雜度也為log（n）。它可以很高效地進(jìn)行區(qū)間統(tǒng)計。在思想上類似于線段樹[8-10]，比線段樹節(jié)省空間，編程復(fù)雜度比線段樹低，但適用范圍比線段樹小。總之樹狀數(shù)組有著簡單易用的特點，容易記憶。

[1]RICHARDABRUALDI.組合數(shù)學(xué)[M].5版.北京：機械工業(yè)出版社，2009：54-55.

[2]王延明.關(guān)于排列逆序數(shù)的進(jìn)一步性質(zhì)及其應(yīng)用[J].棗莊學(xué)院學(xué)報，2007，24（5）：12-13.

[3]張翠，張英瑞.關(guān)于逆序數(shù)相同的n級排列個數(shù)的討論[J].洛陽師范學(xué)院學(xué)報，2010，29（5）：24-25.

[4]周尚超.置換奇偶性的快速算法[J].華東交通大學(xué)學(xué)報，2007，24（1）：87-89.

[5]劉洋.基于紋理合成的圖像修復(fù)與基于分形的圖像分割方法的研究與應(yīng)用[D].吉林：吉林大學(xué)，2010：71-73.

[6]譚浩強.C程序設(shè)計教程[M].北京：清華大學(xué)出版社，2007：33.

[7]錢能.C++程序設(shè)計教程[M].2版.北京：清華大學(xué)出版社，2005：119-122.

[8]林盛華.線段樹在程序設(shè)計中的應(yīng)用[J].大眾科技，2005（4）：68-69.

[9]李博涵，郝忠孝.近似查詢中重疊區(qū)域的掃描計算[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.