树状数组求逆序对

逆序对

设 A 为一个有 n 个数字的有序集 (n>1)，其中所有数字各不相同。
如果存在正整数 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，则 <A[i], A[j]> 这个有序对称为 A 的一个逆序对，也称作逆序数。

树状数组

树状数组(Binary Indexed Tree(BIT), Fenwick Tree)是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之间的所有元素之和，但是每次只能修改一个元素的值；经过简单修改可以在log(n)的复杂度下进行范围修改，但是这时只能查询其中一个元素的值(如果加入多个辅助数组则可以实现区间修改与区间查询)。

经过好长时间查找，终于明白这是怎么做到的

可以参见这里

和这里

其中的离散化说白了就是按大小重新标个号；以"和这里"链接为例
将数列 9 1 0 5 4 离散

然后sort一下

然后重标号

离散到数组里就成了aa[3]=1,aa[2]=2,aa[5]=3,aa[4]=4,aa[1]=5.

然后NOIP2013 DAY1 T2 就出来了：用离散后的第一列火柴给离散后的第二列火柴标号，具体过程略，样例效果就是这样的：

数组aa={0,2,1,3,4,0<repeats ... times>}

NOIP2013 match.cpp

#include<cstdio>
#include<iostream>
#include<algorithm>
#define lowbit(x) (x&(-x))
#define mod 99999997
using namespace std;

int n;
long long ans;
struct N{
    int num,pos;
}a[200000],b[200000];
int tree[200000];
int aa[200000];

bool cmp(const N &x,const N &y){
    return x.num<y.num;
}

void change(int loc,int num){
    int i;
    for(i=loc;i<=n;i+=lowbit(i))
        tree[i]+=num;
}

long long getsum(int loc){
    int i;
    long long res=0;
    for(i=loc;i;i-=lowbit(i))
        res+=tree[i],res%=mod;
    return res;
}

void solve(){
    int i;
    for(i=1;i<=n;i++){
        change(aa[i],1);
        ans+=i-getsum(aa[i]);
        ans%=mod;
    }
    cout<<ans;
}

int main(){
    freopen("match.in","r",stdin);
    freopen("match.out","w",stdout);
    scanf("%d",&n);
    int i;
    for(i=1;i<=n;i++){
        scanf("%d",&a[i].num);
        a[i].pos=i;
    }
    for(i=1;i<=n;i++){
        scanf("%d",&b[i].num);
        b[i].pos=i;
    }
    sort(a+1,a+n+1,cmp);
    sort(b+1,b+n+1,cmp);
    for(i=1;i<=n;i++){
        aa[a[i].pos]=b[i].pos;
    }
    solve();
    return 0;
}

最后

以上就是苗条煎蛋为你收集整理的树状数组求逆序对的全部内容，希望文章能够帮你解决树状数组求逆序对所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。