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

线段树特别适合与区间相关的运算，比如MRQ（minimum range query）求一段区间内的最小值。
BIT可以看作是压缩了的线段树，由于（某类）线段树的右节点可以由父结点和左兄弟求出来，所以右结点就不用存了。
求冒泡排序的交换次数，直观的想可以直接在冒泡排序的过程中计算交换次数，时间复杂度是O（n^2）。交换次数其实是（位置在j的前面，数值还比aj大的数）j从0到n求和。算法的特点是反复对某一区间内的所有元素求和，可以用BIT来优化。
做法是，i从0到n遍历，在循环的某一趟中，dat[ai]表示数字ai的之前出现过的次数，sum（ai）表示在这一趟之前，小于等于ai的数出现的次数。

#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;

}