线段树 BIT 求冒泡排序的交换次数

#include <iostream>
using namespace std;

const int MAX_N = 10000;
int a[MAX_N],n;
int dat[1000000]; // 假定max(a[i])为1000000

//以下是对BIT的实现
int sum(int i){
    int ans = 0;
    while(i>0)
    {
        ans+=dat[i];
        i -= i&-i;
    }
    return ans;
}

void add(int i,int x){
    while(i<=n){
        dat[i] += x;
        i += i&-i;
    }
}

//计算冒泡排序的交换次数
int calu()
{
    cout<<"this is calu"<<endl;
    int ans = 0;
    for(int i=0;i<n;i++)
    {
        ans += i - sum(a[i]);
        add(a[i],1);
    }
    return ans;

}

int main()
{
    cin<<n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    cout<<"ans is "<<calu()<<endl;
    return 0;

}