树状数组（Binary Indexed Tree）是一种利用数的二进制特征进行检索的树状结构。

树状数组是一种奇妙的数据结构，不仅非常高效，而且代码及其简洁。

 

 

 

 

 

 

 

 

#define lowbit(x) ((x)&-(x))

void add(int x,int d){//更新
    while(x<=n){
    tree[x]+=d;
    x+=lowbit(x);      
    }
}

int sum(int x){//求和
    int sum=0;  
    while(x>0){
        sum+=tree[x];
        x-=lowbit(x);
    }
return sum;
}