BIT树状数组求逆序对

BIT 模板库

树状数组求逆序对；
直接按权值排序离散，将位置插入树状数组，该位置的前缀和就是权值比其小而比它大的数的个数

#include<cstdio>
#include<algorithm>
#define MAXN 50000
#define lowbit(x) ((x)&(-x))
int n;
struct data{
    int val,id;
}num[MAXN];
bool cmp(const data &x,const data &y){
    return x.val<y.val;
}
class Binary_Tree{
    private:
        int tree[MAXN];
    public:
        void insert(int pos,int val){
            int i;
            for(i=pos;i<=n;i+=lowbit(i))
                tree[i]+=val;
        }
        int getnum(int pos){
            int i;int ans=0;
            for(i=pos;i;i-=lowbit(i))
                ans+=tree[i];
            return ans;
        }
}BIT;
void solve(){
    int i;int sum=0;
    for(i=1;i<=n;i++){
        BIT.insert(num[i].id,1);
        sum+=i-BIT.getnum(num[i].id);
    }
    printf("%d\n",sum);
}
int main(){
    scanf("%d",&n);
    int i;
    for(i=1;i<=n;i++){
        scanf("%d",&num[i].val);
        num[i].id=i;
    }
    std::sort(num+1,num+n+1,cmp);
    solve();
    return 0;
}