模板：
首先我们先看看树状数组的相关介绍，在我们遇到的题目中，我们可以看到大致一下三类可以用树状数组的类型：1.单点修改+区间查询和（主要） 2.区间修改+单点查询和 3.区间修改+区间查询 4.单点修改+区间查询最大/小值
首先我们先看看树状数组的主要模板：
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
| #include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int n;
int raw_array[N];
int BinaryIndexedtree[N];
int lowbit(int k){
return k&-k;
}
void update(int id,int val){
while(id<=n){
BinaryIndexedtree[id]+=val;
id+=lowbit(id);
}
}
void build(){
for(int i=1;i<=n;i++){
update(i,raw_array[i]);
}
}
int query(int id){
int remain=0;
while(id>0){
remain+=BinaryIndexedtree[id];
id-=lowbit(id);
}
return remain;
}
|
由题易知这道题考察的是单点查询+区间查询和
源码：
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
| #include<bits/stdc++.h>
using namespace std;
int n,m;
int arr1[500003];
long long c[500003];
int lowbit(int x){
return x&-x;
}
void update(int id,int val){
while(id<=n){
c[id]+=val;
id+=lowbit(id);
}
}
long long sum(int id){
long long remain=0;
while(id>0){
remain+=c[id];
id-=lowbit(id);
}
return remain;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&arr1[i]);
update(i,arr1[i]);
}
for(int i=1;i<=m;i++){
int num=0,x=0,k=0;
scanf("%d%d%d",&num,&x,&k);
if(num==1){
update(x,k);
}
else {
printf("%ld\n",sum(k)-sum(x-1));
}
}
return 0;
}
|
易知这道题考察的是区间修改+单点查询，但是我们所熟悉的是单点查询+区间查询，如果单纯用循环套用单点修改来实现区间修改，这就会变成O(MlogN),显然不是最优的选择，我们不妨回归本心，树状数组的优点是可以快速求区间和，以及快速单点修改，那么我们是否可以对原数组进行处理，使得它的区间修改变成单点修改（或者有限且有规律的点修改），这里不妨介绍差分的思路，比如有一个数列arr是{4，3，5，8}我们把它转换为差分化数组arr1就是{4，-1，2，3}，这里有
$$
arr[i]= \sum_{j=1}^{i}{arr1[j]}
$$
这里不得不介绍差分数组的一个特性，即区间同加某一个值的时候只需在左端点加上这个值，在右端点后一个点减去这个值，即实现了区间修改。
我们差分化处理的目的是在区间修改的时候事实上变成了两个端点的单点修改，而利用数组树状的区间求和即实现的单点查询
源码：
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
| #include<bits/stdc++.h>//区间修改+单点查询
using namespace std;
const int maxn=500003;
int n,m;
int arr[maxn],c[maxn];
int lowbit(int x){
return x&-x;
}
void update(int id,int val){
while(id<=n){
c[id]+=val;
id+=lowbit(id);
}
}
int sum(int id){
int remain=0;
while(id>0){
remain+=c[id];
id-=lowbit(id);
}
return remain;
}
int main(){
scanf("%d%d",&n,&m);
int remain1=0;
for(int i=1;i<=n;i++){
int remain=0;
scanf("%d",&remain);
if(i==1){
arr[i]=remain;
}
else{
arr[i]=remain-remain1;//先对原数组进行差分处理
}//差分处理可以让区间修改转化为单点修改，单点查询转换为区间查询。
remain1=remain;
update(i,arr[i]);//生成树状数组
}
/*for(int i=1;i<=n;i++){
printf("%d ",arr[i]);
}
printf("\n");*/
while(m--){
int idx=0;
scanf("%d",&idx);
if(idx==1){
int x=0,y=0,k=0;
scanf("%d%d%d",&x,&y,&k);
update(x,k);
if(y+1<=n)update(y+1,-k);
}
else{
int id=0;
scanf("%d",&id);
printf("%d\n",sum(id));
}
}
return 0;
}
|
例题3:区间修改+区间查询
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
| Problem Description
张煊的金箍棒升级了！
升级后的金箍棒是由N段相同长度的金属棒连接而成（最开始每段金属棒的价值都是1，从1到N编号）；
张煊作为金箍棒的主人，可以对金箍棒任意一段施展魔法操作，每次操作就是将一段连续的金属棒（从X到Y编号）每一段都增加价值Z（Z为1,2,3三种）。
现在，张煊想知道执行M次操作后某一段金箍棒总值。
有Q次查询，每次询问一段（A到B）金箍棒的价值和。
Input
输入的第一行是测试数据的组数（不超过10个）。
对于每组测试数据，第一行包含一个整数N（1 <= N <= 100000），表示金箍棒有N节组成，第二行包含两个整数M（0 <= M <= 100,000）和 Q（1 <= Q <= 100），分别表示执行M次魔法操作，有Q次查询。
接下来的M行，每行包含三个整数X，Y，Z（1 <= X <= Y <= N，1 <= Z <= 3），它定义了一个操作：将从X到Y编号的金属棒每一段的价值增加Z，其中 Z = 1或者 Z = 2 或者 Z = 3。
接下来的Q行，每行包含二个整数A和B（1 <= A <= B <= N），表示查询从A到B这一段金箍棒的价值总和。
Output
对于每组测试数据，请输出Q行，每行一个数字，表示一次查询的结果。
输入样例
1
10
2 2
1 5 2
5 9 3
1 4
3 6
输出样例
12
16
|
由例题二的区间修改+单点查询，我们知道了差分化这个操作，可以将区间修改转化为单点修改。但是如果我们区间查询呢？线段树当然可以完美解决，但是如果我们还是继续使用树状数组呢，树状数组的空间占用大小略优于线段树，可能可以在极限环境帮助我们ac题。
于是我们考虑继续将原数组差分化，先将区间修改优化为单点修改，然后我们开始考虑如何将差分数组的区间求和优化成正常区间求和。我们设普通数组为a[N]，差分数组为d[N]有
$$
a[i]= \sum_{j=1}^i{d[j]}
$$
接着a数组p位置之前的前缀和为
$$
\sum_{i=1}^p{a[i]}=\sum_{i=1}^p\sum_{j=1}^i{d[j]}=\sum_{i=1}^p{(d[i]*(p-i+1))}=(p+1)*\sum_{i=1}^p{d[i]}-\sum_{i=1}^p{(d[i]*i)}
$$
由上溯公式推导结果可知，我们a数组的前缀和可以通过维护两个树状数组c1，c2来实现区间查询转化为单点查询
1
2
| c1[i]的原数组为d[i];
c2[i]的原数组为d[i]*i;
|
源码：
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
| #include<bits/stdc++.h>
using namespace std;
const int N=1e5+8;
int t=0,n=0;
int c1[N],d[N];
long long c2[N];
int lowbit(int k){
return k&-k;
}
void update(int id,int val){
int id1=id;
while(id<=n){
c1[id]+=val;
c2[id]+=id1*val;
id+=lowbit(id);
}
}
long long sum(int id){
long long ans=0,id1=id;
while(id>0){
ans=ans+(id1+1)*c1[id]-c2[id];
id-=lowbit(id);
}
return ans;
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
d[1]=1;
int m,q;
scanf("%d%d",&m,&q);
while(m--){
int x1,y1,z1;
scanf("%d%d%d",&x1,&y1,&z1);
d[x1]+=z1;
d[y1+1]-=z1;
}
for(int i=1;i<=n;i++){
update(i,d[i]);
}
while(q--){
int x1,y1;
scanf("%d%d",&x1,&y1);
printf("%lld\n",sum(y1)-sum(x1-1));
}
memset(c1,0,sizeof(int)*(n+1));
memset(c2,0,sizeof(long long)*(n+1));
memset(d,0,sizeof(int)*(n+2));
}
return 0;
}
|
例题4：单点修改+区间求最大值
如果有一个数列，其中我们有以下两个操作：1.将第i个数修改为k。2.查询[L,R]中的最大值。
你会如何写，我知道你下意识是用线段树，我们仍然ban掉线段树，这不能让你们轻轻松松秒了，显得我很没面子啊www，我们仅使用树状数组，突破常规思维的局限，你会如何完成呢？
首先我们要思考，此时树状数组相当于原函数的意义是什么，一般的树状数组是帮助我们简化修改的次数，以及求和的次数，这里的树状数组却要和最值扯上关系，我们不妨大胆尝试将原来树状数组代表的[id-lowbit(id)+1,id]区间之和重新定义为此区间的最大值，然后每次update树状数组的时候我们先在原数组处直接修改后，再在update的过程中对所有区间包含该点的树状数组和该修改后的值进行一次比较大小
源码：
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
|
#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
int a[N],h[N];
int lowbit(int x){
return x&-x;
}
void updata(int x){
int lx=x;
while(x<=n){
h[x]=max(h[x],a[lx]);
x+=lowbit(x);
}
}
int query(int x,int y){
int ans=0;
while(y>=x){
ans=max(a[y],ans);
y--;
for(;y-lowbit(y)>=x;y-=lowbit(y)){
ans=max(h[y],ans);
}
}
return ans;
}
|
P.S：（其实这个代码有点小问题，就是没考虑我们将一个区间最大值改小的情况qwq，可能需要特判一下，所以大家还是用线段树处理求区间最大值问题吧）