树状数组(一)

模板：

//树状数组    解决动态前缀和问题的数据结构
//树状数组单词查询
int d[maxn],n;

//返回最后一个1的下标
int lowbit(int x){
    return x&(-x);
}
//查询
int query(int x){
    int res=0;
    while(x){
        res+=d[x];
        x-=lowbit(x);
    }
    return res;
}
//修改操作
void add(int x,int v){//对d[i]加v
    while(x<n){
        d[x]+=v;
        x+=lowbit(x);
    }
}