树状数组求逆序数

逆序对：对于$i>j$时，若存在$A[i]<A[j]$则称$<A[i],A[j]>$为一个逆序对
逆序数：数组中所有逆序对的个数

对于需要计算逆序数的数组A[n]，按照数组中元素从大到小的顺序依次插入，这样就能保证先被插入数组的数一定大于当前插入数组的数，接下来就只需要数出在当前插入的位置之前已经出现了多少个数就能得到当前位置的逆序数。

所以可以利用树状数组，每插入一个数就在树状数组的相应位置插入一个1，这样插入位置i的数时，由sum(i-1)就可得出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
int lowbit(int x)
{return x&(-x);}

//向第i个位置添加x
void add(int i,int x)
{
    while(i<=n)
    {
        c[i]+=x;
        i+=lowbit(i);
    }
}

//返回前x项的和
int sum(int x)
{
    int ans=0;
    while(x>0)
    {
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}



//树状数组求逆序数，(i<j && a[i]>a[j])

int inv(int a[],int n){
    int b[n+1]; //存储a数组中第i大的数字的位置
    int res[n+1]={0}; //存储每一位的逆序数
    pair<int,int> p[n+1];
    for(int i=1;i<=n;++i){
        p[i].first=a[i];
        p[i].second=i;
    }
    sort(p+1,p+n+1);
    for(ll i=1;i<=n;++i){
        b[i]=p[n-i+1].second;   
    }

    int ans=0;
    for(int i=1;i<=n;++i){      //把数组a中的数，按照从大到小的顺序插入，用树状数组来统计，第i大的数插入后，在b[i]前有多少个数已经出现
        add(b[i],1);
        res[i]=sum(i-1);
        ans+=res[i];
    }
    return ans;
}