树状数组

前置知识:lowbit运算

\(lowbit(x)\) 表示正整数 \(x\) 在二进制表示下最低位的 \(1\) 跟后面的 \(0\) 构成的数值 ，有 \(lowbit(x)=x\) & $ ($ ~\(~x+1)\) ，即 \(lowbit(x)=x\) & \(-x\)，理由如下：

\(lowbit(x)\) 是最后一位 \(1\) 所以跟前面的位没啥关系，祂在二进制表示下肯定就是 \(1\) 跟上很多 \(0\), 我们将 \(lowbit(x)\) 所在位跟后面拿出来看，毋庸置疑整出来就是 \(lowbit(x)\)

x    : 1 0 0 ... 0 0
~x   : 0 1 1 ... 1 1
~x+1  : 1 0 0 ... 0 0

再说前面的位，每一位肯定是 \(0\) & \(1=0\) 或者 \(1\) & \(0=0\)，对答案没有影响，不用理祂

模板

维护一个数组 \(a\) 的两种操作

• \(a_x\gets a_x+k\)

• 查询 \(\sum\limits_{i=l}^ra_i\)

对于第二个操作，转换一波 \(\sum\limits_{i=l}^ra_i=\sum\limits_{i=1}^ra_i-\sum\limits_{i=1}^{l-1}a_i\) ，变成维护前缀和

BIT

搞一波 $t_x=\sum\limits_{i=x-lowbit(x)+1}^xa_i $，说白了就是用 \(t_x\) 表示以 \(x\) 结尾的长度为 \(lowbit(x)\) 的区间和啊，配上图就变得神奇了，因为祂是一棵树：

对于这棵树，有以下性质

• \(t_x\) 表示区间长度为 \(lowbit(x)\)

• \(x\) 的父节点是 \(x+lowbit(x)\) 即 \(x\) 的子节点是 \(x-lowbit(x)\)

• 树的深度是 \(\log_2n\)

前缀和

考虑查询前缀和 \(\sum\limits_{i=1}^xa_i\) ，根据定义，可以把祂分段搞了，即

套娃之后可以递归或者循环求掉

int ask(int x) {
	int rs=0;
	for( ; x; x-=x&-x) rs+=tr[x];
	return rs;
} 

单点加

考虑单点加操作，观察图，显然与 \(a_x\) 有关的有且仅有 \(x\) 所在那条链，根据上述性质，珂以得出找父节点的办法，就这样一直加上去就珂啦

void add(int x,int w)
	{ for( ; x<=MAXN; x+=x&-x) tr[x]+=w; } 

其中 \(MAXN\) 是上界

理解

本质上是二分（？），此外类似的可以维护最大值