首先先说一下什么是树状数组吧，我理解的应该就是线段树的变形（也可能线段树是树状数组的变形，只不过我先知道的线段数）。其实大概就是把数合组，首先两个合成一组。然后再四个合成一大组，八个合成更大一组，以此类推。然后合成的组可以代替该组的最大标号数据。如图：
然后就是用树状数组求逆序对数了，首先先是建好空的如上图的树状数组（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); }}注：最后关于树状数组访问时和插入一个数据后，如何寻找需要的节点的问题，会找时间证明。
新闻热点
疑难解答
