树状数组（BIT）

BIT常数小！（~~然并卵~~）

思想铺垫:

将一个数$x$化为二进制数$(\overline{a_{k-1}a_{k-2}…a_1a_0})2$ , 并设其中等于1的位是${a{i_1},a_{i_2}…a_{i_m}}$ , 则$x=2^{i_1}+2^{i_2}+…+2^{i_m}$ , 不妨设$i_1>i_2>…>i_m$ , 那么区间$[1,x]$可以拆分成$O(\log_{}{x})$个小区间:

长度为$2^{i_1}$的小区间$[1,2^{i_1}]$
长度为$2^{i_2}$的小区间$[2^{i_1}+1,2^{i_1}+2^{i_2}]$
长度为$2^{i_3}$的小区间$[2^{i_1}+2^{i_2}+1,2^{i_1}+2^{i_2}+2^{i_3}]$;

……
长度为$2^{i_m}$的小区间$[2^{i_1}+2^{i_2}+…+2^{i_{m-1}}+1,2^{i_1}+2^{i_2}+…+2^{i_m}]$

而这些小区间的共同特点是:对于$\forall[x,y ]$ , 其区间长度(记为$|[x,y]|$)就等于”y的二进制拆分下的最小的2的次幂” , 即$lowbit(y)$ .
例如大区间$[1,7]$ , 因为$7=2^{2}+2^{1}+2^{0}$ , 所以被分为三个小区间 : $[1,4]$、$[5,6]$、$[7,7]$ . 而其长度分别是$lowbit(4)=4$、$lowbit(4)=4$、$lowbit(4)=4$
补充——$lowbit()$:
$lowbit(n)$定义为”非负整数$n$在而进制表示下最低位的1及其后的0构成的数的值”. 如$n=22=(10110)_2$ , 则$lowbit(22)=(10)_2=2$
则其代码实现如下:

1
2
3

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

基本思路：

对于给定的原序列$a$ , 我们建立一个数组$c$ , 其中$c[x]$保存原序列$a$的区间$[x-lowbit(x)+1,x]$中所有数的和 , 即$\textstyle\sum_{i=x-lowbit(x)+1}^{x}a[i]$
不难发现 , 数组$c$可以看作一个树形结构 , 且满足如下性质:

每个节点$c[x]$保存以它为根的子树中所有叶节点的和.
每个节点$c[x]$的子节点个数等于$lowbit(x)$的位数 , 如$lowbit(4)=(100)_2$ , 其位数为$3$ , 故$c[4]有3个子节点$.
除树根外 , 每个节点$c[x]$的父节点就是$c[x+lowbit(x)]$.
树的深度为$O(\log_{}{N})$.

如果$n$不是$2$的整数次幂 , 那么树状数组就是一个具有同样性质的森林.
如图:

而树状数组支持的操作有两个:
查询前缀和 : 即找到序列$a$第$1 \sim x$个数的和.

int ask(int x){
	int ans=0;
	for(;x;x-=x&-x) ans+=c[x];	//x&-x即为lowbit(x)
	return ans;
}

若要查询$a$的区间$[l,r]$ , 只需计算$ask(r)-ask(l-1)$.
单点增加 : 给序列中一个数$a[x]$加上y , 不难发现至多只有$\log{}{N}$个节点包含$a[x]$ , 故时间复杂度为$O(\log{}{N})$.

int add(int x,int y){
	for(;x<=N;x+=x&-x) c[x]+=y;
    return ;
}

而在执行操作前 , 我们先要构造出$c$数组.
简单方法是 , 先让$c$全为$0$ , 然后对每个$x$执行$add(x,a[x])$ , 时间复杂度为$O(N\log{}{N})$ , 通常用这种方法就已足够.
更高效的方法是 , 从小到大依次考虑节点$x$ , 借助$lowbit$运算扫描它的子节点求和.若采用这种办法 , 上面树形结构的每条边只会被遍历一次 , 时间复杂度为 $O(\sum_{k = 1} ^ {\log{N}}k * N / 2 ^ {k}) = O(N)$
另外 , 若是题目需要区间增加 , 可以改存$a$的差分数组.

树状数组1
树状数组2