树状数组

共计 513 个字符，预计需要花费 2 分钟才能阅读完成。

树状数组维护的是一个前缀区间

我们观察一个数$n$的二进制，假如这个数是$111_2$，我们想算前$111_2$个数的前缀和，我们就可以将这7个数拆分给$111_2,110_2,100_2$这些编号来进行分配。那么问题就是如何分配数，把哪些数交给谁。

我们观察这个图：

可以发现每个数都分给了 $(x+lowbit(x))$ 对应的编号，我们设$k$为一个二进制数中最低位1所在的二进制位，那么每个编号管理的数的数目就是$2^k$。

$lowbit$函数（提取x对应的低位2次幂）

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

加点

void add(int x,int k){
    while(x<=n){
        s[x] += k ;
        x += lowbit(x) ;
    }
}

查询

int querry(int x){
    int t = 0 ;
    while(x){
        t += s[x] ;
        x -= lowbit(x) ;
    }
    return t ;
}

参考链接

• 树状数组（BIT）
• 图片参考