Si_Yue小屋
0%

SEGMENT_TREE

发表于 更新于 分类于

静态线段树

通过线段树我们可以实现区间维护数据，区间查询数据。

下面给出一个例子，维护了区间和和区间最大值

代码如下：

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <bits/stdc++.h>

using namespace std;

const int MAXN=1e5+2;

typedef long long LL;

//a是原始数据，这里维护区间和和区间最大值，由d和_max表示
//add是加法lazytag，mul是乘法lazytag，cha是改变lazytag，isc是判断是否改变
int a[MAXN],d[MAXN<<2],add[MAXN<<2],mul[MAXN<<2],cha[MAXN<<2],isc[MAXN<<2],_max[MAXN<<2];
int n;

void push_down(LL s,LL t,LL p){
    LL m=s+((t-s)>>1);
    //更新乘法
    if(mul[p]!=1&&s!=t){
        d[p*2]*=mul[p],d[p*2+1]*=mul[p];
        _max[p*2]*=mul[p],_max[p*2+1]*=mul[p];
        mul[p*2]*=mul[p],mul[p*2+1]*=mul[p];
        add[p*2]*=mul[p],add[p*2+1]*=mul[p];
        mul[p]=1;
    }
    //更新加法
    if(add[p]&&s!=t){
        d[p*2]+=add[p]*(m-s+1),d[p*2+1]+=add[p]*(t-m);
        _max[p*2]+=add[p],_max[p*2+1]+=add[p];
        add[p*2]+=add[p],add[p*2+1]=+add[p];
        add[p]=0;
    }
    //更新改变
    if(isc[p]&&s!=t){
        d[p*2]=cha[p]*(m-s+1),d[p*2+1]=cha[p]*(t-s);
        _max[p*2]=_max[p*2+1]=cha[p];
        cha[p*2]=cha[p*2+1]=cha[p];
        isc[p*2]=isc[p*2+1]=1;
        isc[p]=0;
    }
}

void build(LL s,LL t,LL p){
    //建树更新乘法lazytag为1
    mul[p]=1;
    if(s==t){
        //更新维护数据
        d[p]=a[s];
        _max[p]=a[s];
        return;
    }
    LL m=s+((t-s)>>1);
    //递归建树
    build(s,m,p*2);
    build(m+1,t,p*2+1);
    //push_up
    d[p]=d[p*2]+d[p*2+1];
    _max[p]=max(_max[p*2],_max[p*2+1]);
}

void update_mul(LL l,LL r,LL c,LL s,LL t,LL p){
    if(l<=s&&t<=r){
        //区间乘
        d[p]*=c,mul[p]*=c,add[p]*=c;
        _max[p]*=c;
        return;
    }
    LL m=s+((t-s)>>1);
    //push_down
    push_down(s,t,p);
    //递归
    if(l<=m)update_mul(l,r,c,s,m,p*2);
    if(m<r)update_mul(l,r,c,m+1,t,p*2+1);
    //push_up
    d[p]=d[p*2]+d[p*2+1];
    _max[p]=max(_max[p*2],_max[p*2+1]);
}

void update_add(LL l,LL r,LL c,LL s,LL t,LL p){
    if(l<=s&&t<=r){
        //区间加
        d[p]+=c*(t-s+1),add[p]+=c;
        _max[p]+=c;
        return;
    }
    LL m=s+((t-s)>>1);
    //push_down
    push_down(s,t,p);
    //递归
    if(l<=m)update_add(l,r,c,s,m,p*2);
    if(m<r)update_add(l,r,c,m+1,t,p*2+1);
    //push_up
    d[p]=d[p*2]+d[p*2+1];
    _max[p]=max(_max[p*2],_max[p*2+1]);
}

void update_cha(LL l,LL r,LL c,LL s,LL t,LL p){
    if(l<=s&&t<=r){
        //区间改变
        d[p]=c*(t-s+1),cha[p]=c,isc[p]=1;
        _max[p]=c;
        return;
    }
    LL m=s+((t-s)>>1);
    //push_down
    push_down(s,t,p);
    //递归
    if(l<=m)update_cha(l,r,c,s,m,p*2);
    if(m<r)update_cha(l,r,c,m+1,t,p*2+1);
    //push_up
    d[p]=d[p*2]+d[p*2+1];
    _max[p]=max(_max[p*2],_max[p*2+1]);
}

LL getsum(LL l,LL r,LL s,LL t,LL p){
    if(l<=s&&t<=r){
        //区间查询和
        return d[p];
    }
    LL m=s+((t-s)>>1);
    //push_down
    push_down(s,t,p);
    LL sum=0;
    //递归
    if(l<=m)sum+=getsum(l,r,s,m,p*2);
    if(m<r)sum+=getsum(l,r,m+1,t,p*2+1);
    return sum;
}

LL askmax(LL l,LL r,LL s,LL t,LL p){
    if(l<=s&&t<=r){
        //查询最大值
        return _max[p];
    }
    LL m=s+((t-s)>>1);
    //push_down
    push_down(s,t,p);
    LL ret=-0x7fffffff;
    //递归
    if(l<=m)ret=max(ret,askmax(l,r,s,m,p*2));
    if(m<r)ret=max(ret,askmax(l,r,m+1,t,p*2+1));
    return ret;
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        //输入原始数据
        cin>>a[i];
    }
    //建树
    build(1,n,1);
    //test
    cout<<askmax(2,5,1,n,1)<<endl;
    update_cha(1,3,114,1,n,1);
    cout<<askmax(2,5,1,n,1)<<endl;
    update_add(4,6,103,1,n,1);
    cout<<askmax(2,5,1,n,1)<<endl;
    update_mul(2,3,4,1,n,1);
    cout<<askmax(2,5,1,n,1)<<endl;
    return 0;
}

线段树对于区间查询很方便，缺点就是空间开的很大，是原始数据的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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>

using namespace std;

const int MAXN=1e3+2;

struct dynamic_segtree{
    int n,cnt,rt;
    int d[MAXN<<1],ls[MAXN<<1],rs[MAXN<<1];
    #define pushup() d[p]=d[ls[p]]+d[rs[p]]
    #define MID int m=s+((t-s)>>1)
    void change(int x,int c,int s,int t,int& p){
        if(!p)p=++cnt;
        if(s==t){
            d[p]+=c;
            return;
        }
        MID;
        if(x<=m)change(x,c,s,m,ls[p]);
        else change(x,c,m+1,t,rs[p]);
        pushup();
    }

    int getsum(int l,int r,int s,int t,int p){
        if(!p)return 0;
        if(l<=s&&t<=r){
            return d[p];
        }
        MID;
        int sum=0;
        if(l<=m)sum+=getsum(l,r,s,m,ls[p]);
        if(r>m)sum+=getsum(l,r,m+1,t,rs[p]);
        return sum;
    }
};

dynamic_segtree t;

int main(){
    cin>>t.n;
    t.change(1,114,1,t.n,t.rt);
    t.change(2,1919,1,t.n,t.rt);
    t.change(10,1000000,1,t.n,t.rt);
    cout<<t.getsum(1,11,1,t.n,t.rt)<<'\n';
    t.change(10,-1000000,1,t.n,t.rt);
    cout<<t.getsum(1,11,1,t.n,t.rt)<<'\n';
    return 0;
}

动态开点的线段树的左儿子和右儿子是无法直接计算的，所以要用数组去存，然后建立关系是投引用修改即可。

由于是实时开点，有可能走到一个0节点，所以在询问区间和的时候注意在开头判断。

主席树

题目背景

P3834

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
#include <bits/stdc++.h>

using namespace std;

const int MAXN=2e5+2;

struct segtree{
    int d[MAXN<<8],ls[MAXN<<8],rs[MAXN<<8],rt[MAXN<<2],cnt;
    #define pushup() d[p]=d[ls[p]]+d[rs[p]]
    #define MID int m=s+((t-s)>>1)

    void build(int s,int t,int& p){
        p=++cnt;
        if(s==t){
            return;
        }
        MID;
        build(s,m,ls[p]);
        build(m+1,t,rs[p]);
    }

    int change(int x,int c,int s,int t,int _p){
        int p=++cnt;
        ls[p]=ls[_p],rs[p]=rs[_p],d[p]=d[_p];
        if(s==t){
            d[p]+=c;
            return p;
        }
        MID;
        if(x<=m)ls[p]=change(x,c,s,m,ls[p]);
        else rs[p]=change(x,c,m+1,t,rs[p]);
        pushup();
        return p;
    }

    int query(int k,int s,int t,int p1,int p2){
        if(s==t){
            return s;
        }
        MID;
        int tmp=d[ls[p2]]-d[ls[p1]];
        if(tmp>=k)return query(k,s,m,ls[p1],ls[p2]);
        else return query(k-tmp,m+1,t,rs[p1],rs[p2]);
    }
};

int dat[MAXN],tmp[MAXN],n,m,tot;
segtree t;

void init(){
    for(int i=1;i<=n;++i)tmp[i]=dat[i];
    sort(tmp+1,tmp+1+n);
    tot=unique(tmp+1,tmp+1+n)-tmp-1;
    for(int i=1;i<=n;++i){
        dat[i]=lower_bound(tmp+1,tmp+1+tot,dat[i])-tmp;
        t.rt[i]=t.change(dat[i],1,1,tot,t.rt[i-1]);
    }
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>dat[i];
    }
    t.build(t.rt[0],1,tot);
    init();
    for(int i=1,l,r,k;i<=m;++i){
        cin>>l>>r>>k;
        cout<<tmp[t.query(k,1,tot,t.rt[l-1],t.rt[r])]<<'\n';
    }
    return 0;
}