线段树模板

好多的知识都忘了,想当年随手撸主席树的,现在敲个裸线段树卡两小时。。。

题目

hdu1166敌兵布阵

题意

给定n个数,我们有下面的三中操作:

  • 查询一个区间内的和
  • 一个点加上一个数
  • 一个点减去一个数

题解

裸的线段树,也可以用树状数组,树状数组更加的简洁。

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e4+10;
struct Node{
int l, r;
int sum;
Node():sum(0){}
}node[maxn<<2];
int T, n;
int num[maxn];
void push_up(int o){
node[o].sum = node[o<<1].sum+node[o<<1|1].sum;
}
void build(int rt, int l ,int r){
node[rt].l = l;
node[rt].r = r;
if(l == r){
node[rt].sum = num[l];
return;
}
int mid = (l+r)/2;
build(rt<<1, l, mid);
build(rt<<1|1, mid+1, r);
push_up(rt);
}
void update(int rt, int val, int pos){
if(node[rt].l == node[rt].r){
node[rt].sum += val;
return;
}
int mid = (node[rt].l+node[rt].r)/2;
if(pos<=mid){
update(rt<<1, val, pos);
}
else update(rt<<1|1, val, pos);
push_up(rt);
}
int query(int rt, int l, int r){
if(l<=node[rt].l &&r>=node[rt].r){
return node[rt].sum;
}
int mid = (node[rt].l + node[rt].r)/2;
int ret = 0;
//printf("%d\n", mid);
if(l<=mid){
ret+=query(rt<<1, l, r);//注意这里区间的位置,不用修改。
}
if(r>mid){
ret+=query(rt<<1|1, l, r);
}
return ret;
}
int main()
{
scanf("%d", &T);
int tot = 1;
while(T--){
scanf("%d", &n);
for(int i=1; i<=n; i++) scanf("%d", &num[i]);
char s[10];
build(1, 1, n);
// for(int i=1; i<=30; i++){
// printf("%d %d %d\n", node[i].l, node[i].r, node[i].sum);
// }
printf("Case %d:\n", tot++);
while(scanf("%s", s)&&strcmp(s, "End")!=0){
int a, b;
scanf("%d%d", &a, &b);
if(s[0] == 'Q'){
//printf("test: %d %d\n", a, b);
printf("%d\n", query(1, a, b));
}
else if(s[0] == 'A'){
update(1, b, a);
}
else update(1, b*(-1), a);
}
}
return 0;
}

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
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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e4+10;
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r)/2
int a[maxn];
int n;
struct Node{
int sum;
}node[maxn<<2];
void push_up(int rt){
node[rt].sum = node[ls].sum+node[rs].sum;
}
void build(int rt, int l, int r){
node[rt].sum = 0;
if(l == r){
node[rt].sum = a[l];
return ;
}
build(ls, l, mid);
build(rs, mid+1, r);
push_up(rt);
}
void update(int rt, int l, int r, int pos, int val){
if(l>r) return;
if(l == pos && r == pos){
node[rt].sum += val;
return;
}
if(pos<=mid){
update(ls, l, mid, pos, val);
push_up(rt);
}
else if(pos>mid){
update(rs, mid+1, r, pos, val);
push_up(rt);
}
return;
}
int query(int rt, int l, int r, int ql, int qr){
if(l>r) return 0;
if(l == ql&&r == qr){
return node[rt].sum;
}
if(qr<=mid){
return query(ls, l, mid, ql, qr);
}
else if(ql>mid){
return query(rs, mid+1, r, ql, qr);
}
else{
return query(ls, l, mid, ql, mid)+
query(rs, mid+1, r, mid+1, qr);
}
}
int main(){
ios::sync_with_stdio(false);
int t;
cin>>t;
int kase = 1;
while(t--){
cin>>n;
for(int i=1; i<=n; i++){
cin>>a[i];
}
build(1, 1, n);
cout<<"Case "<<kase++<<":"<<endl;
string op;
int u, v;
while(cin>>op){
if(op[0] == 'E') break;
cin>>u>>v;
if(op[0] == 'A'){
update(1, 1, n, u, v);
}else if(op[0] == 'S'){
update(1, 1, n, u, -v);
}
else{
cout<<query(1, 1, n, u, v)<<endl;
}
}
}
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
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 = 5e4+10;
int a[maxn], c[maxn];
int n;
int lowbit(int x){
return x&(-x);
}
void add(int x, int val){
while(x<=n){
c[x] += val;
x += lowbit(x);
}
}
int query(int x){
int ans = 0;
while(x>0){
ans += c[x];
x -= lowbit(x);
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
int t;
cin>>t;
int kase = 1;
while(t--){
cin>>n;
memset(c, 0, sizeof(c));
for(int i=1; i<=n; i++){
cin>>a[i];
}
for(int i=1; i<=n; i++){
add(i, a[i]);
}
string op;
int ans = 0;
int u, v;
cout<<"Case "<<kase++<<":"<<endl;
while(cin>>op){
if(op[0] == 'E') break;
cin>>u>>v;
if(op[0] == 'Q'){
//cout<<query(v)<<endl;
cout<<query(v)-query(u-1)<<endl;
}
else if(op[0] == 'A'){
add(u, v);
}
else add(u, -v);
}
}
return 0;
}

未解决的问题

文章目录
  1. 1. 题目
  2. 2. 题意
  3. 3. 题解
  4. 4. AC代码
  5. 5. 树状数组代码
  6. 6. 未解决的问题
{{ live2d() }}