Burnling's Blog
0%

树状数组

发表于 更新于

原理

行直接拿原图

可以看到，$c_i$ 管理的数的数量就是 $i$ 的二进制表示中最低位的$1$所代表的数字

比如 $(2){10}=(10)_2$，最低位的 $1$ 代表 $2$ ，所以 $c_2$管理 $a_1,a_2$两个数字；$(6){10}=(110)_2$，最低位的 $1$ 表示的也是 $2$ ，所以 $c_6$ 管理 $a_5,a_6$ 两个数字

用法及操作

  • 获取 $i$ 的二进制表示中最低位的 $1$ 所代表的值

    #define lowbit(x) x & -x

    比如 $(22){10}=(10110)_2$，$(-22){10}=(01010)$，所以$(10110)2\And(01010)_2=(00010)_2=(2){10}$

    由于 $-x$ 为 对 $x$ 按位取反后加一得到，

    按位取反后所有的 $1$ 变成 $0$ ，所有的 $0$ 变成 $1$ ，再加上 $1$ 之后会不断向前进位，直到遇到第一个 $0$ 可以“安置”这个不断进位来的 $1$ 。

    而进位的时候低位的 $1$ 又变回了 $0$（与原码相同），进过位的数字只剩下 第一个遇上的 $0$ 变成的 $1$ 与原码同时为 $1$ （因此这部分除了第一个 $0$ 变成的 $1$ 与原码同时为 $1$，其他位均与原码同时为 $0$）

    未进位的更高位的数字由于进行过按位取反且未被进位的 $1$ 影响到，所以这部分进行按位与时均为 $0$

    好像说明白了又好像什么都没说

    再举个栗子，$(44)_{10}=(101100)_2$，对其进行按位取反得到 $(010011)_2$，这个二进制数可以分成两部分来看：010和011，$(011)_2+(001)_2=(100)_2$，进位过的部分现在与原码的这一部分相同，这部分进行按位与的时候100&100=100 ；未进位的前半部分010由于与原码的101是按位取反得到的，所以进行按位与的时候010&101=000，所以这样可以得到最低位的 $1$所代表的值

  • 单点修改

    将一个点的值加上 $k$，管理该点的所有的值都应该加上 $k$

    1
    2
    3
    4
    5
    6
    void add(int x,int k){
        while(x <= n){
            c[x] = c[x] + k;
            x = x + lowbit(x);
        }
    }

  • 前缀求和

    1
    2
    3
    4
    5
    6
    7
    8
    int getSum(int x){
        int ans = 0;
        while(x >= 1){
            ans = ans + c[x];
            x = x - lowbit(x);
        }
        return ans;
    }

  • 区间修改

    维护一个差分数组

    对于序列 $a_1,a_2,a_3,\cdots,a_n$，在区间 $[L,R]$ 内加上 $\Delta$，不难发现：

    • $[L,R]$ 由于加上同一个数，相对大小是不变的，因此 $(L,R]$ 区间内的 $T$ 不需要修改。
    • 而 $TL=a_L-a{L-1}$，$a{L-1}$ 大小不变，只有 $a_L$ 增加了 $\Delta$，因此 $T_L$ 增加了 $\Delta$。同理，$T{R+1}$ 减少 $\Delta$。

    通过上述方法，就可以实现只修改 $TL$和 $T{R+1}$ 共两次就完成了 $[L,R]$ 的区间修改。时间复杂度大大降低。

    我们只需用树状数组维护这个 $T$ 就可以了。

    1
    2
    3
    4
    5
    6
    7
    8
    void add(int x,int k){
        while(x <= n){
            T[x] = T[x] + k;
            x = x + lowbit(x);
        }
    }
    add(l,k);
    add(r+1,-k);

  • 单点查询

    输出差分数组前缀和即可

    1
    2
    3
    4
    5
    6
    7
    8
    int getSum(int x){
        int ans = 0;
        while(x >= 1){
            ans = ans + T[x];
            x = x - lowbit(x);
        }
        return ans;
    }