POJ 2299树状数组求逆序对

求逆序对最常用的方法就是树状数组了，确实，树状数组是非常优秀的一种算法。在做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= 500005;
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 = 0;
    for (i = t; i >= 1; i -= lowbit(i))
        sum += c[i];
    return sum;
}

int main()
{
    int i;
    while (scanf("%d", &n), n)
    {
        //离散化
        for (i = 1; i <= n; i++) 
        {
            scanf("%d", &a[i].v);
            a[i].order = i;
        }
        sort(a + 1, a + n + 1,cmp);
        memset(c, 0, sizeof(c));
        for (i = 1; i <= n; i++)
            aa[a[i].order] = i;
        __int64 ans = 0;
        for (i = 1; i <= n; i++)
        {
            update(aa[i], 1);
            //减去<=的数即为大于的数,即为逆序数
            ans += i - getsum(aa[i]); 
        }
        printf("%I64d
", ans);
    }
    return 0;
}