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

然后就是用樹狀數組求逆序對數了，首先先是建好空的如上圖的樹狀數組（c數組的值都為0，但是樹狀數組的大小已經知道了）。然后一個一個的按照順序添加數（加入j就是把a[j]賦值成1），在這個過程中，每一個瞬間c[i]都表示當前時刻i組（以第i號數為尾的最大組）有多少個數在數組里了。每添加一個a[i]，都會改變若干個c[]數組的值，同時可以確定s[i](該數組在數i前面有多少個比i還小的數)，確定方法，比如：s[6]=c[6]+c[4];s[8]=c[7]+c[6]+c[4];此時也就確定了該數組在第j個數i之前有多少個比它大的數j-s[i]。

總結：這么存這個數的好處就是，有規律的把一串數分成幾個合適大小的組，這樣既不會使得層數太高（比如c[i]表示前i個數怎么怎么樣就是太高了），也可以很方便的訪問幾個連續的數的總結果。

另外關于離散化（我覺得就是把一堆數密集化啊@_@）的問題，我覺得還是用結構體比較方便啊~

關于為什么要是歸并排序而不是冒泡排序：

冒泡排序超時啊，這不是廢話嗎，但是，假如不超時，那么，冒泡排序過程中調換的次數是不是就是最少的相鄰調換次數。每次調換都可以使s--，顯然得出的次數就是逆序對數。那為什么冒泡排序比歸并排序慢呢，簡單一想，肯定是因為做了太多的并不需要交換位置的判斷。

#include<iostream>#include<stdio.h>#include<algorithm>#include<string.h>#define N 500000+500using namespace std;int n;int b[N]={0};//離散化之后的數 bool a[N]={0};//標記數i是否已經在數組里面了 int c[N]={0};//樹狀數組的那個值唄~ int s[N]={0};//數i前面有s[i]個數比它大//int m[N]={0};//數i前面有m[i]個數比它小 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()//預處理，輸入并離散化處理 {	for(int i=1;i<=n;i++)//輸入n個數（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加入到數狀數組中 {	a[x]=1;	int t=x;	while(t<=n)	{		c[t]++;		t+=(t&(-t));	}}int out(int x)//把數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數組第i個數加入到數組中		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);	}}
注：最后關于樹狀數組訪問時和插入一個數據后，如何尋找需要的節點的問題，會找時間證明。