首先先說一下什么是樹狀數(shù)組吧，我理解的應(yīng)該就是線段樹的變形（也可能線段樹是樹狀數(shù)組的變形，只不過我先知道的線段數(shù)）。其實(shí)大概就是把數(shù)合組，首先兩個(gè)合成一組。然后再四個(gè)合成一大組，八個(gè)合成更大一組，以此類推。然后合成的組可以代替該組的最大標(biāo)號(hào)數(shù)據(jù)。如圖：

然后就是用樹狀數(shù)組求逆序?qū)?shù)了，首先先是建好空的如上圖的樹狀數(shù)組（c數(shù)組的值都為0，但是樹狀數(shù)組的大小已經(jīng)知道了）。然后一個(gè)一個(gè)的按照順序添加數(shù)（加入j就是把a(bǔ)[j]賦值成1），在這個(gè)過程中，每一個(gè)瞬間c[i]都表示當(dāng)前時(shí)刻i組（以第i號(hào)數(shù)為尾的最大組）有多少個(gè)數(shù)在數(shù)組里了。每添加一個(gè)a[i]，都會(huì)改變?nèi)舾蓚€(gè)c[]數(shù)組的值，同時(shí)可以確定s[i](該數(shù)組在數(shù)i前面有多少個(gè)比i還小的數(shù))，確定方法，比如：s[6]=c[6]+c[4];s[8]=c[7]+c[6]+c[4];此時(shí)也就確定了該數(shù)組在第j個(gè)數(shù)i之前有多少個(gè)比它大的數(shù)j-s[i]。

總結(jié)：這么存這個(gè)數(shù)的好處就是，有規(guī)律的把一串?dāng)?shù)分成幾個(gè)合適大小的組，這樣既不會(huì)使得層數(shù)太高（比如c[i]表示前i個(gè)數(shù)怎么怎么樣就是太高了），也可以很方便的訪問幾個(gè)連續(xù)的數(shù)的總結(jié)果。

另外關(guān)于離散化（我覺得就是把一堆數(shù)密集化啊@_@）的問題，我覺得還是用結(jié)構(gòu)體比較方便啊~

關(guān)于為什么要是歸并排序而不是冒泡排序：

冒泡排序超時(shí)啊，這不是廢話嗎，但是，假如不超時(shí)，那么，冒泡排序過程中調(diào)換的次數(shù)是不是就是最少的相鄰調(diào)換次數(shù)。每次調(diào)換都可以使s--，顯然得出的次數(shù)就是逆序?qū)?shù)。那為什么冒泡排序比歸并排序慢呢，簡單一想，肯定是因?yàn)樽隽颂嗟牟⒉恍枰粨Q位置的判斷。

#include<iostream>#include<stdio.h>#include<algorithm>#include<string.h>#define N 500000+500using namespace std;int n;int b[N]={0};//離散化之后的數(shù) bool a[N]={0};//標(biāo)記數(shù)i是否已經(jīng)在數(shù)組里面了 int c[N]={0};//樹狀數(shù)組的那個(gè)值唄~ int s[N]={0};//數(shù)i前面有s[i]個(gè)數(shù)比它大//int m[N]={0};//數(shù)i前面有m[i]個(gè)數(shù)比它小 struct shu{	int v;	int ord;}d[N]={0};bool cmp1(shu a,shu b){	if(a.v<b.v)return 1;	else return 0;}void init()//預(yù)處理，輸入并離散化處理 {	for(int i=1;i<=n;i++)//輸入n個(gè)數(shù)（1-n） 	{		scanf("%d",&d[i].v);		d[i].ord=i;	}	sort(d+1,d+n+1,cmp1);	for(int i=1;i<=n;i++)	{		b[d[i].ord]=i;	}}void ceshi1(){	for(int i=1;i<=n;i++)	{		cout<<b[i]<<" ";	}	cout<<endl;}void add(int x)//把x加入到數(shù)狀數(shù)組中 {	a[x]=1;	int t=x;	while(t<=n)	{		c[t]++;		t+=(t&(-t));	}}int out(int x)//把數(shù)x之前(包括x)的所有a都加在一起（即合適的c加到一起） {	int s=0;	while(x>0)	{		s+=c[x];		x=x-(x&(-x));	}		return s;}void sol(){	for(int i=1;i<=n;i++)	{		add(b[i]);//把b數(shù)組第i個(gè)數(shù)加入到數(shù)組中		s[i]=i-out(b[i]);	}}int main(){	while(cin>>n)	{		if(n==0)break;		memset(a,0,sizeof(a));		memset(c,0,sizeof(c));		init();		//ceshi1();		long long int sum=0;		sol();		for(int i=1;i<=n;i++)		{			sum+=s[i];		}		PRintf("%lld/n",sum);	}}
注：最后關(guān)于樹狀數(shù)組訪問時(shí)和插入一個(gè)數(shù)據(jù)后，如何尋找需要的節(jié)點(diǎn)的問題，會(huì)找時(shí)間證明。