这是一道树状数组的模板题,那么既然如此,我来讲讲如何用树状数组来做这道题

关于树状数组的知识点很多,但是,既然这道模板题只考到了树状数组求前缀和和单点修改,那么我这里只说这两个内容

查询前缀和

1
2
3
4
5
6
int ask(int x) {
int ans = 0;
for(;x;x-=x&(-x))
ans+=c[x];
return ans;
}

单点修改

1
2
3
4
void add(int x,int y) {
for(;x<=n;x+=x&(-x))
c[x]+=y;
}

其中,如果你先写个lowbit函数也可以(我没写,可以不用写函数

1
2
3
int lowbit(int x) {
return x&(-x);
}

那么这是我提交的代码

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
#include<bits/stdc++.h>
using namespace std;
int d[500500];
int c[500500];
int n,m;
int ask(int x) {
int ans = 0;
for(;x;x-=x&(-x))
ans+=c[x];
return ans;
}
void add(int x,int y) {
for(;x<=n;x+=x&(-x))
c[x]+=y;
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) {
scanf("%d",&d[i]);
add(i,d[i]);
}
int t1,t2,t3;
int temp1,temp2;
for(int i=1;i<=m;i++) {
scanf("%d%d%d",&t1,&t2,&t3);
if(t1==1) add(t2,t3);
if(t1==2) {
temp1 = ask(t2-1);
temp2 = ask(t3);
printf("%d\n",temp2-temp1);
}
}
return 0;
}

这个代码可以优化在当读入的时候,并不需要保存到一个数组当中,所以可以直接保存在一个临时变量中(可以省一点的空间

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
#include<bits/stdc++.h>
using namespace std;
int writein;
int c[500500];
int n,m;
int ask(int x) {
int ans = 0;
for(;x;x-=x&(-x))
ans+=c[x];
return ans;
}
void add(int x,int y) {
for(;x<=n;x+=x&(-x))
c[x]+=y;
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) {
scanf("%d",&writein);
add(i,writein);
}
int t1,t2,t3;
int temp1,temp2;
for(int i=1;i<=m;i++) {
scanf("%d%d%d",&t1,&t2,&t3);
if(t1==1) add(t2,t3);
if(t1==2) {
temp1 = ask(t2-1);
temp2 = ask(t3);
printf("%d\n",temp2-temp1);
}
}
return 0;
}

好啦,感谢大家阅读我的这篇题解,这是我第一次发布题解,如果有任何问题欢迎与我交流