数据结构——线段树

Posted on | In | Visitors:

This is my blog.
发现教育场可能更适合我
去掌握一个数据结构
很久之前就想学了（估计我是最晚的一个吧）
但是被它的变化给吓倒了
虽然现在还是刚入门
但是板子风格差不多定了
多练练题，尽量背下来吧

basement

线段树是一种二叉搜索树，把区间划分成一些单元区间，每一个区间就是一片叶子
对于每一个非叶子节点，它的左儿子表示的区间为\(\left[ a,\frac{(a+b)}{2} \right] \)，右儿子表示的区间为\(\left[ \frac{(a+b)}{2}+1,b \right] \)。因此线段树是平衡二叉树，最后的子节点数目为N，即整个线段区间的长度。

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e6+5;
const int M = 1e6;
const int Ma = 3e5+5;
ll ans;
ll a[Ma],d[N];
struct Tree{
    ll l,r;
    ll sum,add;
};
Tree tree[Ma<<2];
void pushup(ll root){
    tree[root].sum=tree[root<<1].sum+tree[root<<1|1].sum;
    return ;
}
void pushdown(ll root){
    tree[root<<1].add+=tree[root].add;
    tree[root<<1|1].add+=tree[root].add;
    tree[root<<1].sum+=tree[root].add*(tree[root<<1].r-tree[root<<1].l+1);
    tree[root<<1|1].sum+=tree[root].add*(tree[root<<1|1].r-tree[root<<1|1].l+1);
    tree[root].add=0;
}
void build(ll l,ll r,ll root){
    tree[root].l=l;
    tree[root].r=r;
    if(l==r){
        tree[root].sum=a[l];
        return ;
    }
    ll mid=(l+r)>>1;
    build(l, mid, root<<1);
    build(mid+1, r, root<<1|1);
    pushup(root);
    return ;
}
void update(ll l,ll r,ll root,ll c){
    if(r<tree[root].l||l>tree[root].r) return ;
    if(l<=tree[root].l&&r>=tree[root].r){
        tree[root].add+=c;
        tree[root].sum+=c*(tree[root].r-tree[root].l+1);
        return ;
    }
    if(tree[root].add)pushdown(root);
    ll mid=(tree[root].l+tree[root].r)>>1;
    if(l<=mid)update(l, r, root<<1,c);
    if(r>mid)update(l, r, root<<1|1,c);
    pushup(root);
    return ;
}
void query(ll l,ll r,ll root){
    if(r<tree[root].l||l>tree[root].r)return ;
    if(l<=tree[root].l&&r>=tree[root].r){
        ans+=tree[root].sum;
        return ;
    }
    if(tree[root].add)pushdown(root);
    ll mid=(tree[root].l+tree[root].r)>>1;
    if(l<=mid)query(l, r, root<<1);
    if(r>mid)query(l, r, root<<1|1);
    return ;
}
int main(){
    ios::sync_with_stdio(false);
    ll op,l,r;
    scanf("%lld%lld%lld",&op,&l,&r);
    if(op==1){
        ll add;
        scanf("%lld",&add);
        update(l, r, 1,add);
    }
    else{
        ans=0;
        query(l, r, 1);
        printf("%lld\n",ans);
    }
    
    return 0;
}

后记

很开心，今天算是正式接触线段树了
之前断断续续，也没有什么理解
现在大致有一颗树在脑袋中了
还是starbucks，
还是coding
忙里偷闲
嘻嘻嘻

转载请注明出处，谢谢。

愿 我是你的小太阳



买糖果去喽