线段树模板

ACM

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

题目

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;
}

未解决的问题

本文标题:线段树模板

文章作者:Babydragon

发布时间:2018-01-17, 21:12:38

最后更新:2018-07-27, 20:30:50

原始链接:http://baolintian.github.io/2018/01/17/线段树模板/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

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