树状数组

前言

对于一个序列 a ，我们有两个操作：

• 给定 i，计算 a[1]+a[2]+…+a[i]
• 给定 i,x，执行 a[i]+=x

如果使用普通数组保存序列并实现上述两种操作，则时间复杂度分为别 $O(n)$，$O(1)$

如果使用前缀和数组保存序列并实现上述两种操作，则时间复杂度分为为 $O(1)$，$O(n)$

如果要执行m次这两种种操作，那么总复杂度为 $O(mn)$ ，当 $n$ 或 $m$ 大于 $10^5$ 时，一定会超时

树状数组能够完成两种操作，且时间复杂度均为 $O(\log n)$

原理

二进制拆分

首先对于正整数 $x$ 可以分解为 $x=2^{a_1}+\cdots +2^{a_n}$ ，如 $13=2^0+2^2+2^3$

即 $x$ 可以分解为 $\log x$ 个数字的和。

同样的，一个区间也可以分解成几个区间，我们令这些区间的大小都是2的次幂

如区间 $[1,13]=[1,8]+[9,12]+[13]$

如何把数字和区间联系？

$13=2^0+2^2+2^3$

$1101=1000+100+1$

$[1,1101]=(0,1000]+(1000,1100]+(1100,1101]$

一个区间可以分成多个 $(i-lowbit(i),i]$ 小区间

所以，一个区间为 $[1,x]$ ，可以分为若干个小区间，**每个小区间刚好对应 $x$ 二进制上的每一个 $1$ **

由于对数字进行二进制拆分，能够使用尽可能少的数表示其他的数 (1,2,4可以表示1~7内的所以数)

所以同样思想的树状数组，能够使用尽可能少的区间表示其他区间

存储

如果需要维护长度为 n 的区间，树状数组需要 n 个空间来存储信息。

对于树状数组的每个结点 $c[i]$ ，它记录的区间为 $(i-lowbit(i),i]$

修改

考虑修改a[9]+=x，树状数组中哪些结点会受到影响？a[9]，a[10]，a[12]，a[16]

1001→1010→1100→10000

9+lowbit(9)=10

10+lowbit(10)=12

12+lowbit(12)=16

通过lowbit操作，可以得到修改后受影响的每一个结点

void add(int i, T x) {
	for (; i <= n; i += lowbit(i))
		c[i] += x;
}

查询

考虑查询区间[1,13]，由树状数组中哪些结点组成？c[13]，c[12]，c[8]

13-lowbit(13)=12

12-lowbit(12)=8

8-lowbit(8)=0

通过lowbit操作，可以得到组成查询区间的每一个结点

void get(int i) {
    T s = 0;
	for (; i; i -= lowbit(i))
		s += c[i];
    return s;
}

如果要查询区间 $[l,r]$ ，可以通过 $\mathrm{get}(r)-\mathrm{get}(l-1)$ 来实现，因为 get 本质就是前缀和。