可持久化线段树与标记永久化

数据结构 / 线段树
字数统计: 2.7k   |   阅读时长≈ 13 分钟

点查点修区间历史

主席树维护时间轴和序列轴

P3919 【模板】可持久化线段树 1（可持久化数组） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

今天写这道板子题，一开始我一直想不明白。为什么两个操作都是单点，要用线段树来维护，没有更方便的方法吗？

后来我想明白了，最暴力的写法是每次操作都复制一整个数组，这样内存肯定爆。如何优化呢，关键在于复用。

下图演示是最暴力的方法，红色方框代表修改的节点。显然，我们无法直接复用第一次的蓝色头结点，因为里面的内容有过修改。我们将要把每一个节点依次复制，就很麻烦，时间上就过不了。

一种很容易想到的优化就是，我们直接复用之前的，但把修改的内容记录下来，查询之前看看有没有修改过。但修改的内容多了之后，每次查询要花费很久。

再进一步优化，我们不用一个数组指向所有节点。而是用一种数据结构，每个节点只维护接下来一半的节点。这样我们就可以很容易的复用那些没有被修改过的节点。显然这就是线段树。

题目示意图和代码如下

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
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
struct node {
    int ls,rs,val;
    int id;
}tree[N<<5];
int cnt;
int head[N];
int a[N];
void build(int &p, int l, int r){
    p = ++cnt;
    if(l == r){
        tree[p].val = a[l];
        return;
    }
    int mid =  (l+r)>>1;
    build(tree[p].ls, l, mid);
    build(tree[p].rs, mid+1, r);
}
void update(int &p, int pre, int l, int r, int index, int val){
    p = ++cnt;
    tree[p] = tree[pre];
    if(l == r){
        tree[p].val = val;
        return;
    }
    int mid = (l+r)>>1;
    if(index <= mid) update(tree[p].ls, tree[pre].ls, l, mid, index, val);
    else update(tree[p].rs, tree[pre].rs, mid+1, r, index, val);
}
int query(int p, int l, int r, int index){
    if(l == r) return tree[p].val;
    int mid = (l + r) >> 1;
    if(index <= mid) return query(tree[p].ls, l, mid, index);
    else return query(tree[p].rs, mid + 1, r, index);
}

int main(){
    ios::sync_with_stdio (0);
    cin.tie (0);
    cout.tie (0);
    int n,m;
    cin>>n>>m;
    for(int i = 1; i <= n; i++){
        cin>>a[i];
    }
    build(head[0], 1, n);
    int cur = 1;
    for(int i = 1; i <= m; i++){
        int op, pre;
        cin>>pre>>op;
        if(op == 1){
            int index, val;
            cin>>index>>val;
            update(head[i], head[pre], 1, n, index, val);
        }else{
            int index;
            cin>>index;
            cout<<query(head[pre], 1, n, index)<<endl;
            head[i] = head[pre];
        }
    }
    return 0;
}

讲一下代码为什么要写build。如果写的是动态开点权值线段树，我们可以不用build，使用如下

1
2
3
4
5
6
7
8
9
10
11
void insert(ll& p,ll l,ll r,ll x,ll k){
    if(!p) p = ++cnt;
    if(l == r){
        tree[p].sum += k;
        return;
    }
    ll mid = (l + r)/2;
    if(x <= mid) insert(tree[p].l,l,mid,x,k);
    else insert(tree[p].r,mid+1,r,x,k);
    tree[p].sum += k;
}

注意这和我们主席树的代码有什么不一样？不一样就在这一句

1
if(!p) p = ++cnt;

在主席树中，我们没有判断！p。这是为什么呢？

这是因为主席树每次都要依赖上一个树来构建，我走的那条链，就是要修改的。链上的所有节点都要更新。整个流程就是，我一边走一边复制pre节点的内容，再把我经过的节点id全部改变。可以参考p3，粉色的就是我新开出来的链。

而动态开点是，开出我没有的点，我经过的点已经开过了，就没必要再开了。

而且你主席树代码的update是要接受pre节点的，你得先有个原树，才能接受。要么你另外写一个change函数，和动态开点那个update一样的，一个个传进去就不用build了。

总结就是，主席树的update依赖于pre树，开出一条新链，所以不能直接在这里初始化。

静态区间第 𝑘小

主席树维护序列轴和值域轴

记得主席树的主节点开个head维护一下。

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>
#define endl '\n'
using namespace std;
const int N = 2e5 + 5;
const int M = 1e9 + 5;
struct node {
    int ls,rs,sum,id;
}tree[N<<6];
int cnt;
void update(int &p, int pre, int l, int r, int x){
    p = ++cnt;
    tree[p] = tree[pre];
    tree[p].sum = tree[pre].sum + 1; //标记永久化的写法
    if(l == r){
        // tree[p].sum = tree[pre].sum + 1;  //pushup的写法
        return;
    }
    int mid = (l+r)>>1;
    if(x <= mid) update(tree[p].ls, tree[pre].ls, l, mid, x);
    else update(tree[p].rs, tree[pre].rs, mid+1, r, x);
    // tree[p].sum = tree[tree[p].ls].sum + tree[tree[p].rs].sum;  //pushup的写法
}

int query(int L, int R, int l, int r, int k){ //二分找到最大节点
    if(l == r) return l;
    int mid = (l+r)>>1;
    int left_sum = tree[tree[R].ls].sum - tree[tree[L].ls].sum;
    if(k <= left_sum) return query(tree[L].ls, tree[R].ls, l, mid, k);
    else return query(tree[L].rs, tree[R].rs, mid+1, r, k-left_sum);
}
int head[N];
int main(){
    ios::sync_with_stdio (0);
    cin.tie(0), cout.tie(0);
    int n,m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        int x;
        cin>>x;
        update(head[i], head[i-1], 0, M, x);
    }
    for(int i = 1; i <= m; i++){
        int L,R,k;
        cin >> L >> R >> k;
        cout<<query(head[L-1], head[R], 0, M, k)<<endl;
    }
    return 0;
}

标记永久化

回想我们之前处理线段树的方法，我们在遍历到叶子后，要pushup一层层把值上传更新。在有区间修改的操作时，我们需要加上pushdown操作，每次查询和修改都要把影响下推。但是在主席树中，我们有一个特点，就是共用节点。

所以我们采取一种新的方法，不需要pushup和pushdown，我们只要帮每次的修改记录下来，在查询的时候算上去就行了。这就是标记永久化

主席树加标记永久化的板子

TTM - To the moon - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

讲解一下标记永久化的部分，先看update

1
2
3
4
5
6
7
8
9
10
11
12
13
//标记直接打上，子节点打上标记后的影响也直接计算，相当于直接pushup了
void update(ll& p, ll pre, ll l, ll r, ll L, ll R, ll d){
    p = ++cnt;
    tree[p] = tree[pre];
    tree[p].sum += (min(r, R) - max(l, L) + 1) * d; //要把子节点标记的影响算进来，有点类似pushup。这里要在if之前，可以自己想一下。
    if(l >= L && r <= R){
        tree[p].add += d; //直接累加标记
        return;
    }
    ll mid = (l+r)>>1;
    if(L <= mid) update(tree[p].l, tree[pre].l, l, mid, L, R, d);
    if(R > mid) update(tree[p].r, tree[pre].r, mid+1, r, L, R, d);
}

然后是query

1
2
3
4
5
6
7
8
9
10
11
12
13
//关键就是，把一路上的标记的影响累加下来，最后一起计算就可以了。
//相当于pushdown一样
ll query(ll p, ll l, ll r, ll L, ll R, ll add){
    if(L <= l && r <= R){
        return tree[p].sum + (r-l+1)*add;
    }
    ll ans = 0;
    add += tree[p].add; //这里却不用放在if上面，可以想想为什么
    ll mid = (l+r)>>1;
    if(L <= mid) ans += query(tree[p].l, l, mid, L, R, add);
    if(R > mid) ans += query(tree[p].r, mid+1, r, L, R, add);
    return ans;
}

总结来说就是，sum是考虑节点变化后的节点和，但他的父节点怎么改他并不知道。所以要靠查询的时候，把父节点的修改带下来。

全部代码如下

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
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;
const ll N = 1e5 + 5;
ll a[N], head[N];
struct node{
    ll l,r,sum,add;
}tree[N<<6];
ll cnt;
void build(ll& p, ll l, ll r){
    p = ++cnt;
    if(l == r){
        tree[p].sum = a[l];
        return;
    }
    ll mid = (l+r)>>1;
    build(tree[p].l, l, mid);
    build(tree[p].r, mid+1, r);
    tree[p].sum = tree[tree[p].l].sum + tree[tree[p].r].sum;
}
void update(ll& p, ll pre, ll l, ll r, ll L, ll R, ll d){
    p = ++cnt;
    tree[p] = tree[pre];
    tree[p].sum += (min(r, R) - max(l, L) + 1) * d;
    if(l >= L && r <= R){
        tree[p].add += d;
        return;
    }
    ll mid = (l+r)>>1;
    if(L <= mid) update(tree[p].l, tree[pre].l, l, mid, L, R, d);
    if(R > mid) update(tree[p].r, tree[pre].r, mid+1, r, L, R, d);
}

ll query(ll p, ll l, ll r, ll L, ll R, ll add){
    if(L <= l && r <= R){
        return tree[p].sum + (r-l+1)*add;
    }
    ll ans = 0;
    add += tree[p].add;
    ll mid = (l+r)>>1;
    if(L <= mid) ans += query(tree[p].l, l, mid, L, R, add);
    if(R > mid) ans += query(tree[p].r, mid+1, r, L, R, add);
    return ans;
}
int main(){
    ios::sync_with_stdio (0);
    cin.tie(0), cout.tie(0);
    ll n,m;
    cin>>n>>m;    
    for(ll i = 1; i <= n; i++){
        cin>>a[i];
    }
    build(head[0], 1, n);
    ll t = 0;
    ll cur = 0;
    while(m--){
        char op;
        cin>>op;
        if(op == 'C'){  
            ll l,r,d;
            cin>>l>>r>>d;
            t++;
            update(head[t], head[t-1], 1, n, l, r, d);
        }else if(op == 'Q'){
            ll l,r;
            cin>>l>>r;
            cout<<query(head[t], 1, n, l, r, 0)<<endl;
        }else if(op == 'H'){
            ll l,r,t;
            cin>>l>>r>>t;
            cout<<query(head[t], 1, n, l, r, 0)<<endl;
        }else{
            cin>>t;
        }
    }
    return 0;
}

静态区间第k大

jscpc的E题，思路稍微转一下就是求区间第k大了。和第k小很像

Problem - E - Codeforces

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
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct node {
    int ls, rs, sum;
}tree[N<<6];
int cnt;
void update(int& cur, int pre, int l, int r, int x){
    cur = ++cnt;
    tree[cur] = tree[pre];
    tree[cur].sum++;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(x <= mid) update(tree[cur].ls, tree[pre].ls, l, mid, x);
    else update(tree[cur].rs, tree[pre].rs, mid + 1, r, x);
}
int query(int L, int R, int l, int r, int k){
    if(l == r) return l;
    int right_sum = tree[tree[R].rs].sum - tree[tree[L].rs].sum;
    int mid = (l + r) >> 1;
    if(k <= right_sum) return query(tree[L].rs, tree[R].rs, mid + 1, r, k);
    else return query(tree[L].ls, tree[R].ls, l, mid, k - right_sum);
}

int head[N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, m;
    cin>>n>>m;
    for(int i = 1; i <= n; i++){
        int x;
        cin>>x;
        update(head[i], head[i-1], 0, 1e5, x);
        while(x >>= 1) update(head[i], head[i], 0, 1e5, x);
    }
    for(int i = 1; i <= m; i++){
        int L, R, k;
        cin>>L>>R>>k;
        cout<<query(head[L - 1], head[R], 0, 1e5, k+1)<<endl;
    }
    cout<<log2(100000);
}
  • Copyrights © 2023-2024 Kano
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信