Eternity

Until The End

可持久化线段树(主席树)

发表于 更新于 分类于 ，
本文字数： 6.1k 阅读时长 ≈ 6 分钟

“人最重要的，是不能忘记自己为何出发。”

可持久化数据结构

一种数据结构可持久化，当其满足本身的拓扑结构不变时，其可持久化。

因此，$\text{Trie}$ 树，线段树，树状数组，平衡树等都支持可持久化。

类似于 $\text{Github}$ 的 git 操作。——$\text{Yxc}$

可持久化数据结构用于支持存储该数据结构的所有历史版本。

假设有 $\mathcal O(m)$ 次操作，那么就会有 $m+1$ 个历史版本，如果每一个版本都去 $\text{copy}$ 一份的话，空间复杂度会高达 $\mathcal O(n(m+1))$ ，那么，可持久化的核心思想就是只去记录每一个版本被修改过的点，即与前一个版本不同的结点。

介绍

主席树全称可持久化权值线段树，用于维护区间最值与一些奇奇怪怪的东西。支持历史询问与修改（目前不会），似乎与普通线段树的时间复杂度是一样的，但空间会减少很多消耗。

在算法执行的过程中，会发现在更新一个动态集合时，需要维护其过去的版本。这样的集合称为是可持久的。

实现

建树(build)

首先，建立起亘古树，即一开始的整棵线段树。但是根本不需要。对于主席树而言，改掉了我的一个习惯：即线段树的左区间与右区间是存于 $Tree$ 内的。这样可能会消耗一些空间。但对于主席树而言，其儿子节点并不满足 Tree[p].l=p<<1 与 Tree[p].r=p<<1|1 的关系，所以对于建树而言，每一个节点的 $l$ 和 $r$ 存储的是其左右儿子的点编号。每输入一个数，就动态修改即可，根本不需要进行 $build$ 操作。一般不建

修改/插入(modify)

每输入一个值……其实这句话是不对的。对于部分主席树的题而言，是需要离散化的。所以插入（修改）操作都是在输入完并离散化之后才一次性完成的。

以洛谷的模板题为例，我们需要求区间 $[l,r]$ 的第 $k$ 小值。则对于这道题的历史版本 $v_i$ ，处理的其实是前缀和的信息。即我们建的第 $i$ 个树存储的是区间 $[1,i]$ 的 $Val$ 信息。而叶节点存储的则是第 $i$ 个数的个数。

对于每一次的插入操作，我们就在原来基础上插入一条链直达叶节点，表示我们在该位置插入了一个数。然后自下而上更新区间值 $dat$ ，这与线段树是一样的。而不同的是，在插入过程中，其节点编号 $p$ 是动态的。因为当一个地方没有被修改时，我们会指向其历史编号，只有当修改时才会新建编号，而我们新建了编号后，其父节点所指的子节点也是会更改的。所以就会有 int &x 的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
inline void underModify(int &x,int l,int r,int d)
{
    Tree[++Idx]=Tree[x];
    x=Idx;
    if(l==r)
    {
        ++Tree[x].dat;
        return ;
    }
    int mid=(l+r)>>1;
    if(d<=mid) underModify(Tree[x].l,l,mid,d);
    else underModify(Tree[x].r,mid+1,r,d);
    underPushUp(x);
}

查询(query)

其意义并非真正的线段树查询。因为用了二分的思想又与线段树相似而称之为查询。对于查询第 $k$ 小数而言，因为我们已经离散化排了序的，则：

  1. 当该节点的左儿子存储的数的个数大于 $k$ ，则查询左儿子；
  2. 当该节点的左儿子存储的数的个数小于 $k$ ，则查询右儿子的第 $k-ls$ 小值。

这就因题而异了，只是提一句。

初始化

离散化

因题而异。可以有，也可以没有。

排序

因题而异。可以有，也可以没有。

修改根节点(root)

每一个历史线段树的根节点在一开始的时候都是空的，其会在插入操作里不断更新。这也是为什么 int &x 的原因（二次重提）

AC Code

查看代码 
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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define underMax(x,y) ((x)>(y)?(x):(y))
#define underMin(x,y) ((x)<(y)?(x):(y))
typedef long long ll;
using namespace std;
const int MAXN=1e6+1;
template<class T>
inline void underRead(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
int N,M,Val[MAXN<<1],Root[MAXN<<1];
struct PersistentSegmentTree
{
    int dat,l,r;
}Tree[MAXN<<4];
int Idx;
inline void underPushUp(int p)
{
    Tree[p].dat=Tree[Tree[p].l].dat+Tree[Tree[p].r].dat;
}
inline void underModify(int &x,int l,int r,int d)
{
    Tree[++Idx]=Tree[x];
    x=Idx;
    if(l==r)
    {
        ++Tree[x].dat;
        return ;
    }
    int mid=(l+r)>>1;
    if(d<=mid) underModify(Tree[x].l,l,mid,d);
    else underModify(Tree[x].r,mid+1,r,d);
    underPushUp(x);
}
inline int underQuery(int x1,int x2,int l,int r,int k)
{
    if(l==r) return l;
    int mid=(l+r)>>1;
    int ls=Tree[Tree[x2].l].dat-Tree[Tree[x1].l].dat;
    if(k<=ls) return underQuery(Tree[x1].l,Tree[x2].l,l,mid,k);
    else return underQuery(Tree[x1].r,Tree[x2].r,mid+1,r,k-ls);
}
int main()
{
    // freopen("PST.in","r",stdin);
    // freopen("PST.out","w",stdout);
    vector<int>V;
    underRead(N),underRead(M);
    for(int i=1;i<=N;++i) 
    {
        underRead(Val[i]);
        V.push_back(Val[i]);
    }
    sort(V.begin(),V.end());
    int len=V.erase(unique(V.begin(),V.end()),V.end())-V.begin();
    for(re int i=1;i<=N;++i)
    {
        Root[i]=Root[i-1];
        underModify(Root[i],1,len,lower_bound(V.begin(),V.end(),Val[i])-V.begin()+1);
    }
    for(int Ql,Qr,Qk;M;M--)
    {
        underRead(Ql),underRead(Qr),underRead(Qk);
        printf("%d\n",V[underQuery(Root[Ql-1],Root[Qr],1,len,Qk)-1]);
    }
    return 0;
}
/*
5 5
25957 6405 15770 26287 26465 
2 2 1
3 4 1
4 5 1
1 2 2
4 4 1
*/

可持久化数组

其实差不多，只是多了一个建树操作。因为它有一个初始数列，这道题真的就是字面意思的可持久化了。

P3919 【模板】可持久化线段树 1（可持久化数组）

AC Code

查看代码 
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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define underMax(x,y) ((x)>(y)?(x):(y))
#define underMin(x,y) ((x)<(y)?(x):(y))
typedef long long ll;
using namespace std;
const int MAXN=1e6+1;
template<class T>
inline void underRead(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
int N,M,Idx,Root[MAXN];
struct SegmentTree
{
    int l,r,dat;
}Tree[MAXN*100];
int Val[MAXN],op,Ql,Qv,Qk;
inline void underBuild(int &x,int l,int r)
{
    x=++Idx;
    if(l==r)
    {
        Tree[x].dat=Val[l];
        return ;
    }
    int mid=(l+r)>>1;
    underBuild(Tree[x].l,l,mid),underBuild(Tree[x].r,mid+1,r);
}
inline void underModify(int &x,int l,int r,int d,int k)
{
    Tree[++Idx]=Tree[x];
    x=Idx;
    if(l==r)
    {
        Tree[x].dat=k;
        return ;
    }
    int mid=(l+r)>>1;
    if(d<=mid) underModify(Tree[x].l,l,mid,d,k);
    else underModify(Tree[x].r,mid+1,r,d,k);
}
inline int underQuery(int x,int l,int r,int d)
{
    if(l==r) return Tree[x].dat;
    int mid=(l+r)>>1;
    if(d<=mid) return underQuery(Tree[x].l,l,mid,d);
    else return underQuery(Tree[x].r,mid+1,r,d);
}
int main()
{
    // freopen("PST-fake.in","r",stdin);
    // freopen("PST-fake.out","w",stdout);
    underRead(N),underRead(M);
    for(int i=1;i<=N;++i) underRead(Val[i]);
    underBuild(Root[0],1,N);
    for(int i=1;i<=M;++i)
    {
        underRead(Qv),underRead(op);
        Root[i]=Root[Qv];
        if(op==1)
        {
            underRead(Ql),underRead(Qk);
            underModify(Root[i],1,N,Ql,Qk);
        }
        else
        {
            underRead(Ql);
            printf("%d\n",underQuery(Root[i],1,N,Ql));
        }
    }
    return 0;
}
/*
5 10
59 46 14 87 41
0 2 1
0 1 1 14
0 1 1 57
0 1 1 88
4 2 4
0 2 5
0 2 4
4 2 1
2 2 2
1 1 5 91
*/
相关文章