【存模闆】樹狀數組

一維

int lowbit(int x){
    return x&-x;
}
int sum(int x){
    int ret=;
    while(x){
        ret+=c[x];
        x-=lowbit(x);
    }
    return ret;
}
void update(int x,int d){
    while(x<=n){
        c[x]+=d;
        x+=lowbit(x);
    }
}
           

二維

inline int lowbit(int x){
    return x&-x;
}
void update(int x,int y,int d){
    for(;x<=s;x+=lowbit(x))
        for(int j=y;j<=s;j+=lowbit(j))
            c[x][j]+=d;
}
int getsum(int x,int y){
    int ret=,j;
    for(;x;x-=lowbit(x))
        for(j=y;j;j-=lowbit(j))
            ret+=c[x][j];
    return ret;
}