引入
树状数组和线段树具有相似的功能,但他俩毕竟还有一些区别:树状数组能有的操作,线段树一定有;线段树有的操作,树状数组不一定有。但是树状数组的代码要比线段树短,思维更清晰,速度也更快,在解决一些单点修改的问题时,树状数组是不二之选。
过程
下面这张图展示了树状数组的工作原理:
这个结构和线段树有些类似:用一个大节点表示一些小节点的信息,进行查询的时候只需要查询一些大节点而不是所有的小节点。
最上面的八个方块就代表数组 aaa。
他们下面的参差不齐的剩下的方块就代表数组 aaa 的上级—— ccc 数组。
从图中可以看出: 管理的是 c2c_2c2 a1a_1a1,a2a_2a2;
c4c_4c4 管理的是 a1a_1a1,a2a_2a2,a3a_3a3,a4a_4a4;
c6c_6c6 管理的是 a5a_5a5,a6a_6a6;c8c_8c8 则管理全部 888 个数。
如果要计算数组 aaa 的区间和,比如说要算 a51a_{51}a51 ~ a91a_{91}a91 的区间和,可以采用类似倍增的思想:
从 919191 开始往前跳,发现 cnc_ncn( n 我也不确定是多少,算起来太麻烦,就意思一下)只管 a91a_{91}a91 这个点,那么你就会找 a90a_{90}a90 ,发现 cn−1c_{n-1}cn−1 管的是 a90a_{90}a90&a89a_{89}a89;那么你就会直接跳到 a88a_{88}a88,cn−2c_{n-2}cn−2 就会管 c81c_{81}c81~c88c_{88}c88 这些数,下次查询从 a80a_{80}a80 往前找,以此类推。
用法及操作
那么问题来了,怎么知道 cic_ici 管理的数组 aaa 中的哪个区间呢? 这时,我们引入一个函数——lowbit:
int lowbit(int x) {// x 的二进制表示中,最低位的 1 的位置。// lowbit(0b10110000) == 0b00010000// ~~~^~~~~// lowbit(0b11100100) == 0b00000100// ~~~~~^~~return x & -x;
}
注释说明了 lowbit 的意思,对于 x=88x=88x=88:88(10)=1011000(2)88_{(10)}=1011000_{(2)}88(10)=1011000(2)
发现第一个 111 以及他后面的 000 组成的二进制是 100010001000
1000(2)=8(10)1000_{(2)}=8_{(10)}1000(2)=8(10)
100010001000 对应的十进制是 888,所以 c88c_{88}c88 一共管理 888 个 aaa 数组中的元素。 事实上,cic_ici 代表的区间就是 [i−lowbit(i)+1,i][i-lowbit(i)+1,i][i−lowbit(i)+1,i]。
在常见的计算机中,有符号数采用补码表示。在补码表示下,数 x 的相反数 -x = ~x + 1。
使用 lowbit 函数,我们可以实现很多操作,例如单点修改,将 axa_xax 加上 kkk,只需要更新 axa_xax 的所有上级:
void add(int x, int k) {while (x <= n) { // 不能越界c[x] = c[x] + k;x = x + lowbit(x);}
}
前缀求和:
int getsum(int x) { // a[1]..a[x]的和int ans = 0;while (x >= 1) {ans = ans + c[x];x = x - lowbit(x);}return ans;
}