ACM数据结构-树状数组

模板：

int n;
int tree[LEN];

int lowbit(int x){
    return x&-x;
}

void update(int i,int d){//index,delta
    while(i<=n){
        tree[i]+=d;
        i+=lowbit(i);
    }
}

int getsum(int i){
    int ans=;
    while(i>){
        ans+=tree[i];
        i-=lowbit(i);
    }
    return ans;
}

示意图：

1.Ultra-QuickSort

大佬代码：

//树状数组  
    #include<iostream>  
    #include<string.h>  
    #include<algorithm>  
    using namespace std;  
    #define MAX 500010  
    int c[MAX];  
    int aa[MAX];  
    int n;  
    typedef struct nano{  
        int val;  
        int order;  
    }node;  
    node in[MAX];  
    int lowbit(int x)  
    {  
        return x&(-x);  
    }  
    void update(int x,int val)  
    {  
        while(x<=n){  
            c[x]+=val;  
            x+=lowbit(x);  
        }  
    }  
    int sum(int x)  
    {  
        int s=;  
        while(x>=)  
        {  
            s+=c[x];  
            x-=lowbit(x);  
        }  
        return s;//一开始竟然忘记写了这个语句，还以为树状数组写错了呢  
    }  
    bool cmp(node a,node b){  
        return a.val<b.val;  
    }  
    int main(int argc, char *argv[])  
    {  
        //freopen("2299.in", "r", stdin);  
        while(scanf("%d",&n)==&&n){  
            for(int i=;i<=n;++i)  
            {  
                scanf("%d",&in[i].val);  
                in[i].order=i;  
            }  
            sort(in+,in+n+,cmp);  
            for(int i=;i<=n;++i)  
                aa[in[i].order]=i;//离散化到小范围来  
            memset(c,,sizeof(c));  
            long long ans=;  
            for(int i=;i<=n;++i)  
            {  
                update(aa[i], );  
                ans+=(i-sum(aa[i]));  
            }  
            printf("%lld\n",ans);  
        }  
        return ;  
    }

大佬代码理解：

首先用结构体ｎｏｄｅ：{ｖａｌ，ｏｒｄｅｒ}来存输入信息，用sort(in+1,in+n+1,cmp); 来根据ｖａｌ值进行排序，通过代码

for(int i=;i<=n;++i)  
            aa[in[i].order]=i;

构造数组ａａ，ａａ表示第ｉ个数排第ａａ［ｉ］位。（代码理解：ｉ表示原本的索引，in[i].order表示排序后的索引）

逆序数计算：

for(int i=;i<=n;++i)  
        {  
            update(aa[i], );  
            ans+=(i-sum(aa[i]));  
        }

ａｎｓ增量：索引ｉ之前比他大的数。