树状数组的两个操作:快速的求前缀和(查询操作),修改操作,两个操作的进行过程最多只有log(x)次,树状数组下标一定是从一开始的
线段数组中的lowbit函数,lowbit函数就是返回一个数的二进制数的从右往左数的第一位1
例如:2的二进制数是10,那么10(二级制)转换成十进制是2,所以树状数组c[2] = 2;
再比如:6的二进制数是110,那么取从右往左数的第一个1,然后取右边的0的位数,即10(二进制)转换成(十进制)2,所以树状数组c[6] = 2
所有的以四的倍数的数的lowbit函数的值就是它本身;
以lowbit函数算出所有树状数组的区间长度,如图
区间长度是以右端点的二进制从右往左数的第一位1的位置到最右边的数,取出来之后转换成十进制之后就是区间长度
例如:Cx = ....01111 ,所以区间(左开右闭)
1.(....01110,....01111]
2.(....01100,....01110]
3.(....01000,....01100]
4.(....00000,....01000]
树状数组求前缀和就是用父节点找子节点,二进制表示的数....01111,从右往左数,每有一个1就有一个子节点,求前缀和就找一个子节点就删掉一个,直到找到祖宗节点
求x的前缀和用代码实现x的前缀和: x = a[x] + c[x - 1] + c[x - 1] - lowbit(x - 1) + .... + c ;
通过子节点找父节点,对应修改操作->将父节点找子节点逆过来即可;
x : ....011110000 -> p:....100000000 ;
x的二进制零的位置加上一个lowbit(x)直到变成p
这是一个迭代的过程,通过子节点一直修改直到父节点,修改一个数会影响到它的父节点,找父节点的过程中是唯一的
当a[x] += x时,for(int i = x ; i <= n;i += lowbit(x)) c[i] += x;
查询操作(求前缀和):求1->x的和,从右往左找,以x为父节点,将x转化成二级制数,然后再通过父节点去找子节点,二进制每有一个1,就代表有一个子节点,x的二进制就减去一个lowbit(x)
for(int i = x;i;i -= lowbit(x)) res += c[i];
强
用一下 md 语法和 LateX 会更棒
感谢大佬的宝贵意见,蒟蒻第一次发分享,本蒟蒻也会参照其他大佬的分享。