求逆序对最常用的方法就是树状数组了，确实，树状数组是非常优秀的一种算法。在做POJ2299时，接触到了这个算法，理解起来还是有一定难度的，那么下面我就总结一下思路：
首先：因为题目中a[i]可以到999,999,999之多，在运用树状数组操作的时候，用到的树状数组C[i]是建立在一个有点像位存储的数组的基础之上的，不是单纯的建立在输入数组之上。
比如输入一个9 1 0 5 4（最大9）
那么C[i]树状数组的建立是在：
下标 0 1 2 3 4 5 6 7 8 9 –——下标就要建立到9
数组 1 1 0 0 1 1 0 0 0 1 –——通过1来表示存在
现在由于999999999这个数字相对于500000这个数字来说是很大的，所以如果用数组位存储的话，那么需要999999999的空间来存储输入的数据。 这样是很浪费空间的，题目也是不允许的，所以这里想通过离散化操作。
那么怎么离散化操作呢？离散化是一种常用的技巧，有时数据范围太大，可以用来放缩到我们能处理的范围，必要的是建立一个结构体a[n]，v表示输入的值，order表示原i值，再用一个数组aa[n]存储离散化后的值
例如：
i:1 2 3 4 5
v:9 0 1 5 4
sort:0 1 4 5 9
order:2 3 5 4 1
aa:5 1 2 4 3 //建立映射:aa[a[i].order]=i;
即原本的9经过排序应该在第5位，现在aa[1]=5，对应原来的9，大小次序不变，只是将9缩小到了5
那么离散化之后怎么求逆序对呢？首先是通过update函数插入一个数，比如update(2,1),一开始都c[n]为0,插入后+1
现在其余的为0，c[2],c[4]=1,这就说明前面下标为2处有一个数2，这里是关键，c[4]=1不代表下标为4时有一个数4，它的意思是在4之前的区间内所有元素之和是1，即有一个数2，具体的可以看看树状图
然后只有用getsum实时求出插入一个数的前面有几个数，就可以算出当前小于等于这个数的数的个数，再通过下标i-getsum(aa[i]),得到大于它的数目，即为逆序数。
上面样例的解释:
i:1 2 3 4 5
aa:5 1 2 4 3
i=1->插入aa[1]
调用upDate(5, 1),把第5位设置为1
1 2 3 4 5
0 0 0 0 1
计算1-5上小于等于5的数字存在么？ 这里用到了树状数组的getSum(5) =1操作
现在用输入的下标1 - getSum(5) = 0 就可以得到对于5的逆序数为0。
i=2-> 插入aa[2]
调用upDate(1, 1),把第1位设置为1
1 2 3 4 5
1 0 0 0 1
注意这里实际输出的是11 0 1 1,但就像上面说的这里真正的含义是只插入1这个数
c[4],c[2]只是因为前面c[1]变化才变化的，而且变化了也不要紧，通过后面的getsum求的总是区间的和
后面计算时,只计算c[4]的值,前面是不加上去的,而c[4]的值就是前面到4所以出现的数的和
计算1-1上小于等于1的数字存在么？ 这里用到了树状数组的getSum(1)= 1操作
现在用输入的下标2 - getSum(2) = 1 就可以得到对于1的逆序数为1。
i=3-> 插入aa[3]
调用upDate(2, 1),把第2位设置为1
1 2 3 4 5
1 1 0 0 1
计算1-2上小于等于2的数字存在么？ 这里用到了树状数组的getSum(2)= 2操作
现在用输入的下标3 - getSum(2) = 1 就可以得到对于2的逆序数为1。
i=4->插入aa[4]
调用upDate(4, 1),把第4位设置为1
1 2 3 4 5
1 1 0 1 1
计算1-4上小于等于4的数字存在么？ 这里用到了树状数组的getSum(4)= 3操作
现在用输入的下标4 - getSum(2) = 1 就可以得到对于4的逆序数为1。
i=5-> 插入aa[5]
调用upDate(3, 1),把第3位设置为1
1 2 3 4 5
1 1 1 1 1
计算1-3上小于等于3的数字存在么？ 这里用到了树状数组的getSum(3)= 3操作
现在用输入的下标5 - getSum(3) = 2 就可以得到对于2的逆序数为2。
总逆序数为上述逆序数之和,即0+1+1+1+2=5
POJ2299代码如下：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std; //aa[] : 离散化后的数组
//c[] : 树状数组
const int maxn= ;
int aa[maxn];
int c[maxn];
int n; //v : value
//order : 输入时的相对次序
struct Node
{
int v;
int order;
}a[maxn]; bool cmp(Node a, Node b)
{
return a.v < b.v;
} int lowbit(int k)
{
return k&(-k);
} void update(int t, int value)
{
//即一开始都为0，一个个往上加(+1)
int i;
for (i = t; i <= n; i += lowbit(i))
c[i] += value;
} int getsum(int t)
{
//即就是求和函数，求前面和多少就是小于它的个数
int i, sum = ;
for (i = t; i >= ; i -= lowbit(i))
sum += c[i];
return sum;
} int main()
{
int i;
while (scanf("%d", &n), n)
{
//离散化
for (i = ; i <= n; i++)
{
scanf("%d", &a[i].v);
a[i].order = i;
}
sort(a + , a + n + ,cmp);
memset(c, , sizeof(c));
for (i = ; i <= n; i++)
aa[a[i].order] = i;
__int64 ans = ;
for (i = ; i <= n; i++)
{
update(aa[i], );
//减去<=的数即为大于的数,即为逆序数
ans += i - getsum(aa[i]);
}
printf("%I64d\n", ans);
}
return ;
}