防止日后忘记。
引入
例题 $1$：
已知一个数列，你需要进行下面两种操作：
- 将某一个数加上 $x$。
- 求出某区间每一个数的和。
对于操作 $1$，我们可以直接通过普通数组 $\mathcal O(1)$ 实现修改。
对于操作 $2$，我们可以通过前缀和 $\mathcal O(1)$ 实现查询。
然而，若使用普通数组，查询复杂度为 $\mathcal O(n)$；若使用前缀和数组，修改复杂度为 $\mathcal O(n)$。
而树状数组就是一种兼具修改、查询的高效数据结构，修改、查询复杂度均为 $\mathcal O(\log n)$。
事实上，树状数组能解决的问题是线段树能解决的问题的子集：树状数组能做的，线段树一定能做；线段树能做的，树状数组不一定可以。然而，树状数组的代码要远比线段树短，时间效率常数也更小，因此仍有学习价值。
原理
维护可差分信息
普通树状数组维护的信息及运算要满足 结合律 且 可差分，如加法（和）、乘法（积）、异或等。
- 结合律：$(x\circ y)\circ z=x\circ (y\circ z)$，其中 $\circ$ 是一个二元运算符。
- 可差分：具有逆运算的运算，即已知 $x\circ y$ 和 $x$ 能求出 $y$。
区间划分
将一段长度为 $n$ 的前缀 $[1,n]$ 划分为不超过 $\log n$ 段区间，那么我们仅仅需要合并这 $\log n$ 段区间的信息即可直到原来需要合并 $n$ 个元素才能知道的信息（比如前缀和），而在修改时也仅仅需要至多修改 $\log n$ 段区间，从而使得修改、查询复杂度均为 $\mathcal O(\log n)$。
如图：
如何划分
令树状数组所使用数组为 $t$。
那么 $t[x]$ 表示的就是 $\large \sum\limits_{i=x-\operatorname{lowbit}(x)+1}^{x}a[i]$。
$\operatorname{lowbit(x)}$
在树状数组中，$\operatorname{lowbit}(x)$ 为 $x$ 的二进制最低位的 $1$ 的位权，数值上为 x&-x。
比如说，$x=5$，$x$ 的二进制为 $100_{(2)}$，则 $\operatorname{lowbit}(x)=2^2=4$。
而 x&-x 的原理也很简单。首先你要知道在计算机中，数字以补码的形式存储。
（此处的二进制数有效位数只有 $4$ 位，最高位为符号位）
那么对于正数（树状数组中 $\operatorname{lowbit}(x)$ 只会出现正数，见下文），其补码就是符号位 $0$ 接上其二进制；例如 $5$，就是 $0100_{(2)}$。
而负数呢？
先是一个符号位 $1$，随后是二进制逐位取反，最后在加 $1$。那么 $-5$ 的补码便是 $1011{(2)}+1=1100{(2)}$。
可以发现，此时 x&-x 的确是 $100_{(2)}=2^2=4$。
因为在 $\operatorname{lowbit}(x)$ 的后面全是 $0$，取反得到的全是 $1$，然后再加 $1$，因此 $\operatorname{lowbit}(x)$ 所在位仍然是 $1$，而前面按位取反，全部不一样。
故 $\operatorname{lowbit}(x)$ 为 x&-x。
参考代码
1
2
3
int lowbit(int x){
return x&-x;
}
区间长度
每一个 $t[x]$ 所表示的区间长度均为 $2^k$，$k$ 为自然数。
那么这个 $2^k$ 也即 $\operatorname{lowbit}(x)$。
区间查询与单点修改（树状数组 1）
区间查询
普通树状数组维护数组，每次查询 $query(x)$ 的值都是区间 $[1,x]$ 的值，想要查询 $[l,r]$，$query(r)-query(l)$ 即可（此处维护的是前缀和，其余同理）。
那么 $query(x)$ 是如何工作的呢？
上文中提到，每一个 $t[x]$ 维护的区间长度均为 $\operatorname{lowbit}(x)$，也即 $[x-\operatorname{lowbit}(x)+1,x]$。
那么我们令 $x\leftarrow x-\operatorname{lowbit}(x)$ 直到 $x=0$ 即可。
这样，我们就能够在 $\mathcal O(\log n)$ 的时间内查询。
参考代码
1
2
3
4
5
6
7
int query(int x){
int sum=0;
while(x){
sum+=t[x];
x-=lowbit(x);
}return sum;
}
单点修改
若是一个值 $a[x]$ 修改了，那么包含其值的 $t[y]$ 必然也需要修改。
而 $t[x]$ 被 $t[x+\operatorname{lowbit}(x)]$ 包含。
证明：
令 $y=x+\operatorname{lowbit}(x)$，$x=p\times 2^{k+1}+2^k$，其中 $k$ 为自然数，$s$ 为实数。
则 $y=(p+1)\times 2^{k+1},y-\operatorname{lowbit}(y)+1=p\times 2^{k+1}+1$。
考虑到 $x-\operatorname{lowbit}(x)+1=p\times 2^k+1$，因此 $y-\operatorname{lowbit}(y)+1<x-\operatorname{lowbit}(x)+1$。
又考虑到 $y$ 显然大于 $x$，因此 $t[x]$ 被 $t[x+\operatorname{lowbit}(x)]$ 包含。
因此，我们仅仅需要令 $x\leftarrow x+\operatorname{lowbit}(x)$ 直到 $x>n$ 即可。
参考代码
1
2
3
4
5
6
void add(int x,int k){
while(x<=n){
t[x]+=k;
x+=lowbit(x);
}
}
例题 AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
const int N=5e5;
int n,m,op,x,k,t[N+1];
int lowbit(int x){
return x&-x;
}
void build(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&x);
t[i]+=x;
int j=i+lowbit(i);
if(j<=n)t[j]+=t[i];
}
}
void add(int x,int k){
while(x<=n){
t[x]+=k;
x+=lowbit(x);
}
}
int query(int x){
int sum=0;
while(x){
sum+=t[x];
x-=lowbit(x);
}return sum;
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
build();
while(m--){
scanf("%d %d %d",&op,&x,&k);
switch(op){
case 1:
add(x,k);
break;
case 2:
printf("%d\n",query(k)-query(x-1));
break;
}
}
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
单点查询与区间修改（树状数组 2）
这很简单，同样以前缀和为例。
你只需要维护一个一阶差分数组即可。
比如你要给区间 $a[l,r]$ 加上 $5$，那么在差分数组 $b$ 上你只需要： \(b[l]\leftarrow b[l]+5\\ b[r+1]\leftarrow b[r+1]-5\) 这样就维护了区间修改。
对于单点查询，$a[x]$ 的值显然就是 $\sum\limits_{i=1}^x b[x]$，树状数组维护 $b$ 的前缀和即可。
例题 AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
const int N=5e5;
int n,m,op,x,y,k,b[N+1];
int lowbit(int x){
return x&-x;
}
void build(){
int x0=0;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&x);
b[i]+=x-x0;
x0=x;
int j=i+lowbit(i);
if(j<=n)b[j]+=b[i];
}
}
void add(int x,int k){
while(x<=n){
b[x]+=k;
x+=lowbit(x);
}
}
int query(int x){
int sum=0;
while(x){
sum+=b[x];
x-=lowbit(x);
}return sum;
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
build();
while(m--){
scanf("%d %d",&op,&x);
switch(op){
case 1:
scanf("%d %d",&y,&k);
add(x,k);add(y+1,-k);
break;
case 2:
printf("%d\n",query(x));
}
}
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
区间修改与区间查询
这是个问题，我们以守墓人为例题。
我当时为那道题写了一个简单的个人记录：
对于数组 $a$ 的差分数组 $d$，我们可以使用 $d$ 求出 $a$ 的前缀和数组 $s$。
由于 $d_k=a_k-a_{k-1}$，则： \(a_k=d_1+d_2+d_3+\cdots+d_k\) 那么： \(\begin{aligned} s_k&=a_1+a_2+a_3+\cdots+a_k\\ &=d_1+(d_1+d_2)+(d_1+d_2+d_3)+\cdots+(d_1+d_2+d_3+\cdots+d_k)\\ &=k\times d_1+(k-1)\times d_2+(k-2)\times d_3+(k-3)\times d_4+\cdots+d_k\\ &=(k+1)(d_1+d_2+d_3+\cdots+d_k)-(1\times d_1+2\times d_2+3\times d_3+\cdots+k\times d_k)\\ &=(k+1)\sum_{i=1}^k d_i-\sum_{i=1}^k d_i\times i \end{aligned}\)
维护树状数组 $d_i=a_i-a_{i-1}$ 和树状数组数组 $c_i=d_i\times i$ 即可。
关于各个操作：
- 差分处理
- 由1同理
- 由1同理
- 计算前缀和
- 由4同理
首先，需要明确的是，单点操作可以视为长度为 $1$ 的区间操作。
因此原题中的有效操作就两个：
- 操作 $1$：将区间 $a[l,r]$ 加上 $k$。
- 操作 $4$：求 $\sum\limits_{i=l}^r a_i$。
我们可以维护一个一阶差分数组 $d$ 。
那么，对于区间修改，我们仅仅需要像上一种情况中那样： \(d[l]\leftarrow d[l]+k\\ d[r+1]\leftarrow d[r+1]-k\) 但是区间查询呢？
对于单点查询，可以通过 $query(x)$ 实现 $\mathcal O(\log n)$，但是显然不可能遍历 $[l,r]$，每次都调用查询，因为这样是 $\mathcal O(n\log n)$ 的。
这时候就需要用到我们上面的个人记录中的结论了。我们可以使用 $d$ 数组求出前缀和数组，前缀和数组上相减即可。
具体参见代码。
例题 AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
const ll N=2e5;
ll n,f,a[N+1],d[N+1],c[N+1];
ll lowbit(ll x){
return x&-x;
}
void build(ll a[]){
for(int i=1;i<=n;i++){
int j=i+lowbit(i);
if(j<=n)a[j]+=a[i];
}
}
void add(ll x,ll k){
ll pl=x;
while(x<=n){
d[x]+=k;
c[x]+=pl*k;
x+=lowbit(x);
}
}
ll query(ll x){
ll sum=0,pl=x+1;
while(x){
sum+=pl*d[x]-c[x];
x-=lowbit(x);
}return sum;
}
void s1(){
ll l,r,k;
scanf("%lld %lld %lld",&l,&r,&k);
add(l,k);
add(r+1,-k);
}
void s2(){
ll k;
scanf("%lld",&k);
add(1,k);
add(2,-k);
}
void s3(){
ll k;
scanf("%lld",&k);
add(1,-k);
add(2,k);
}
void s4(){
ll l,r;
scanf("%lld %lld",&l,&r);
printf("%lld\n",query(r)-query(l-1));
}
void s5(){
printf("%lld\n",query(1));
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
scanf("%lld %lld",&n,&f);
for(int i=1;i<=n;i++){
scanf("%lld",a+i);
d[i]=a[i]-a[i-1];
c[i]=d[i]*i;
}build(d);build(c);
while(f--){
ll op;
scanf("%lld",&op);
switch(op){
case 1:s1();break;
case 2:s2();break;
case 3:s3();break;
case 4:s4();break;
case 5:s5();break;
}
}
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
技巧
树状数组的清空（时间戳优化）
清空树状数组是 $\mathcal O(n)$ 的，因此在多组数据时，这是一种常用的技巧。
即定义数组 $tag[i]$ 表示 $t[i]$ 的值是第几组数据的，若 $i$ 不为当前数据组编号，则 $t[i]$ 的值即初始值 $0$（或其他初始值）。
