算法笔记：可持久化数据结构

狠补一下一些不太熟的东西。

可持久化线段树#

可持久化数组 #

要求维护一个数组，进行 $m$ 次操作，每次操作都生成一个新的版本（版本编号从 $1$ 到 $m$ ）。操作如下：

① 在某个给定历史版本上的基础上，该版本修改某个数的值。

② 在某个给定历史版本的基础上，该版本不修改任何值，但要求查询第 $x$ 个数。

朴素的实现肯定是爆时间空间的。考虑有什么方法维护，可持久化线段树可以维护。对于线段树，单次修改实际上只修改了一个长度为 $\log n$ 的路径。那我们重新建树就行了，每次的新树，继承了前一个版本的树的剩余节点，新增的节点只有 $\log n$ 个。

1
template<typename T>
2
class PersistentArray {
3
private:
4
    struct Node {
5
        T val;
6
        int l, r;
7
        int lson, rson;
8
    };
9

10
    vector<Node> node;
11
    vector<int> root;
12
    vector<T> data;
13

14
    /* 克隆当前节点，返回新节点的索引 */
15
    int clone(int base) {
16
        node.push_back(node[base]);
17
        return node.size() - 1;
18
    }
19

20
    /* 创建新节点，返回新节点的索引 */
21
    int create(T val, int l, int r, int lson, int rson) {
22
        node.push_back({val, l, r, lson, rson});
23
        return node.size() - 1;
24
    }
25

26
    /* 建立持久化数组的初始版本 */
27
    int build(int l, int r) {
28
        if (l == r)
29
            return create(data[l], l, r, -1, -1);
30
        else {
31
            int mid = (l + r) / 2;
32
            int lson = build(l, mid);
33
            int rson = build(mid + 1, r);
34
            return create(0, l, r, lson, rson);
35
        }
36
    }
37

38
    /* 修改持久化数组路径 */
39
    int revise_path(int u, int pos, const T val) {
40
        int p = clone(u);
41
        if (node[u].l == node[u].r)
42
            node[p].val = val;
43
        else {
44
            int mid = (node[u].l + node[u].r) / 2;
45
            if (pos <= mid)
46
                node[p].lson = revise_path(node[u].lson, pos, val);
47
            else
48
                node[p].rson = revise_path(node[u].rson, pos, val);
49
        }
50
        return p;
51
    }
52

53
    /* 查询持久化数组的某个版本的值 */
54
    T ask_path(int u, int pos) {
55
        if (node[u].l == node[u].r)
56
            return node[u].val;
57
        else {
58
            int mid = (node[u].l + node[u].r) / 2;
59
            if (pos <= mid)
60
                return ask_path(node[u].lson, pos);
61
            else
62
                return ask_path(node[u].rson, pos);
63
        }
64
    }
65

66
public:
67
    PersistentArray(vector<T>& initData) {
68
        data = initData;
69
        // 好像不加这个会RE
70
        node.reserve(32 * initData.size());
71
        root.reserve(initData.size()); // 预留空间
72
        root.push_back(build(0, data.size() - 1));
73
    }
74

75
    /* 修改指定版本的数组并返回新版本号 */
76
    int revise(int v, int pos, const T val) {
77
        root.push_back(revise_path(root[v], pos, val));
78
        return root.size() - 1;
79
    }
80

81
    /* 查询指定版本的数组的某个位置的值 */
82
    T ask(int v, int pos) {
83
        return ask_path(root[v], pos);
84
    }
85

86
    /* 复制一个版本（不修改）并返回版本号 */
87
    void copy(int v) {
88
        root.push_back(root[v]);
89
    }
90
};

静态区间第 $k$ 小问题 #

前置：权值线段树

给定 $n$ 个整数构成的序列 $a$ ，多次询问，将对于指定的闭区间 $[l, r]$ 查询其区间内的第 $k$ 小值。

假设我们对整个数组查询第 $k$ 小，会怎么做？排序一遍，然后从小到大就是了。如果我们只需单次查询，那就给定了区间 $[l,r]$ 后，同样的，对原先数组排序一遍，然后从小到大遍历排序后的全数组，对于每个元素检查原始位置是否在 $[l,r]$ 中，直到找到 $[l,r]$ 中的第 $k$ 小。

但是如果需要多次查询就比较麻烦了。我们单次查询的复杂度已经到了 $O(n\log n)$ ，进行 $q$ 次查询，复杂度会到 $O(q\cdot n\log n)$ ，是比较坏的。因此，有一个想法就是，我们只做一次 $[1,n]$ 的查询，能不能通过这一次的查询，预处理构造出一个数据结构，让我们能满足比较快的对 $[l,r]$ 的查询？我们考虑记录一下 $n$ 次插入的每次插入后的版本。很明显我们可以对这 $n$ 次插入后的版本二分查询 $[l,r]$ 中是否已经插入了 $k$ 个元素，然后对恰好插入了 $k$ 个元素的那个版本的线段树，查询 $[l,r]$ 当前的最大值，也就是第 $k$ 小元素。

这个思路的问题是，我们要建立 $n$ 个线段树，包爆空间的。

如何解决？可以考虑复用数据结构。也就是说，考虑到每次创建一个新版本的线段树，和前一个版本的区别只在于插入了一个新的节点，也就是说线段树上有且仅有一个路径发生了更改。那我们创建新树的时候，只需要创建一个新的根节点，然后创建这个路径即可，其他的部分，我们直接指针指回上一个版本的节点即可。这就可以很大节省空间。

也就是说，要建立一个可持久化的权值线段树，维护每个版本的区间的权值。对于从小到大的每个数 $x$ 和它原先的位置 $pos$ ，我们把它的位置 $pos$ 插入这个权值线段树。

这题也要加离散化会快一点，但是我用了个很快的快读能过。

1
#include <bits/stdc++.h>
2
using namespace std;
3
const int maxn=1e5;
4

5
int n,q;
6

7
/* 可持久化权值线段树 */
8
template <typename T>
9
class CountSegmentTree{
10
private:
11
    struct Node {
12
        int cnt;          // 节点权值
13
        T l, r;       // [l,r]
14
        int lson, rson; // 左右儿子
15
    };
16

17
    struct Version{
18
        int root; // 根节点编号
19
        T revise_val;   // 这个版本与前一个版本相比修改的数
20
        int revise_cnt;   // 修改的权值数
21
    };
22
    vector<Node> node;          // 节点列表
23
    vector<Version> version;   // 版本信息存储
24

25
    int create(int val,T l,T r,int lson,int rson) {
26
        node.push_back({val,l,r,lson,rson});
27
        return node.size()-1;
28
    }
29
    int clone(int u){
30
        node.push_back(node[u]);
31
        return node.size()-1;
32
    }
33
    /* 建树，区间[l,r] */
34
    int build(T l,T r) {
35
        if (l==r)
36
            return create(0,l,r,-1,-1);
37
        else {
38
            T mid=(l+r)/2;
39
            return create(0,l,r,build(l,mid),build(mid+1,r));
40
        }
41
    }
42

43
    /* 对val值的所有路径节点修改x */
44
    void revise(T val,int x){
45
        int u=version.back().root;  // 默认从最后一个版本开始修改
46
        int *fa=nullptr;
47
        while (true){
48
            int v=clone(u);
49
            if (fa)
50
                *fa=v;
51
            else
52
                version.push_back(Version{v,val,x});
53
            node[v].cnt+=x;
54
            if (node[u].l==node[u].r)
55
                return ;
56
            T mid=(node[u].l+node[u].r)/2;
57
            u=(val<=mid)?node[u].lson:node[u].rson;
58
            fa=(val<=mid)?(&node[v].lson):(&node[v].rson);
59
        }
60
    }
61
    /* 查询区间权值 */
62
    int ask_range(int u,const T l,const T r){
63
        if (l<=node[u].l&&node[u].r<=r)
64
            return node[u].cnt;
65
        T mid=(node[u].l+node[u].r)/2;
66
        int ret=0;
67
        if (l<=mid)
68
            ret+=ask_range(node[u].lson,l,r);
69
        if (r>mid)
70
            ret+=ask_range(node[u].rson,l,r);
71
        return ret;
72
    }
73

74
public:
75
    CountSegmentTree(T l, T r){
76
        // 传入开的桶的范围，[L,R]
77
        node.reserve((r-l+5)*32);
78
        version.push_back(Version{build(l,r),0});
79
    }
80
    /* 插入值val，返回版本号 */
81
    int insert(T val){
82
        revise(val,1);
83
        return version.size()-1;
84
    }
85
    /* 删除值val，返回版本号 */
86
    void remove(T val){
87
        revise(val,-1);
88
        return version.size()-1;
89
    }
90
    /* 查询版本[L,R]的数的个数 */
91
    int ask_cnt(int ver, T l, T r){
92
        return ask_range(version[ver].root,l,r);
93
    }
94
    /* 查询版本[L,R]修改权值的数 */
95
    T ask_version_diff(int ver){
96
        return version[ver].revise_val;
97
    }
98
};
99

100
namespace fastio
101
{
102
    const int bufl=1<<16;
103
    const double base1[16]={1,1e-1,1e-2,1e-3,1e-4,1e-5,1e-6,1e-7,1e-8,1e-9,1e-10,1e-11,1e-12,1e-13,1e-14,1e-15};
104
    const double base2[16]={1,1e1,1e2,1e3,1e4,1e5,1e6,1e7,1e8,1e9,1e10,1e11,1e12,1e13,1e14,1e15};
105
    struct IN{
106
        FILE *IT;char ibuf[bufl],*is=ibuf,*it=ibuf;
107
        IN(){IT=stdin;}IN(char *a){IT=fopen(a,"r");}
108
        inline char getChar(){if(is==it){it=(is=ibuf)+fread(ibuf,1,bufl,IT);if(is==it)return EOF;}return *is++;}
109
        template<typename Temp>inline void getInt(Temp &a){a=0;int b=0,c=getChar();while(c<48||c>57)b^=(c==45),c=getChar();while(c>=48&&c<=57)a=(a<<1)+(a<<3)+c-48,c=getChar();if(b)a=-a;}
110
        IN& operator>>(char &a){a=getChar();return *this;}
111
        IN& operator>>(char *a){do{*a=getChar();}while(*a<=32);while(*a>32)*++a=getChar();*a=0;return *this;}
112
        IN& operator>>(string &a){char b=getChar();while(b<=32)b=getChar();while(b>32)a+=b,b=getChar();return *this;}
113
        IN& operator>>(int &a){getInt(a);return *this;}
114
        IN& operator>>(long long &a){getInt(a);return *this;}
115
    };
116
    struct OUT{
117
        FILE *IT;char obuf[bufl],*os=obuf,*ot=obuf+bufl;int Eps;long double Acc;
118
        OUT(){IT=stdout,Eps=6,Acc=1e-6;}OUT(char *a){IT=fopen(a,"w"),Eps=6,Acc=1e-6;}
119
        inline void ChangEps(int x=6){Eps=x;}
120
        inline void flush(){fwrite(obuf,1,os-obuf,IT);os=obuf;}
121
        inline void putChar(int a){*os++=a;if(os==ot)flush();}
122
        template<typename Temp>inline void putInt(Temp a){if(a<0){putChar(45);a=-a;}if(a<10){putChar(a+48);return;}putInt(a/10);putChar(a%10+48);}
123
        OUT& operator<<(char a){putChar(a);return *this;}
124
        OUT& operator<<(char *a){while(*a>32)putChar(*a++);return *this;}
125
        OUT& operator<<(string a){for(auto c:a)putChar(c);return *this;}
126
        OUT& operator<<(int a){putInt(a);return *this;}
127
        OUT& operator<<(long long a){putInt(a);return *this;}
128
        ~OUT(){flush();}
129
    };
130
}
131
using fastio::IN;
132
using fastio::OUT;
133
IN fin;
134
OUT fout;
135

136
int main(){
137
//  freopen("P3834_9.in","r",stdin);
138
//  freopen("P3834_9.txt","w",stdout);
139
  fin>>n>>q;
140
    typedef pair<int,int> P;
141
    vector<int> x(n+1);
142
    vector<P> a(n);
143
    for (int i=0;i<n;i++){
144
      fin>>a[i].first;
145
        a[i].second=i+1;
146
        x[i+1]=a[i].first;
147
    }
148
    sort(a.begin(),a.end());
149
    CountSegmentTree<int> tree(1,n);
150
    for (P p: a)
151
        tree.insert(p.second);
152
    int L,R,k;
153
    int l,r,mid;
154
    while (q--){
155
      fin>>L>>R>>k;
156
        l=0,r=n;
157
        while (r-l>1){
158
            mid=(l+r)>>1;
159
            if (tree.ask_cnt(mid,L,R)>=k)
160
                r=mid;
161
            else
162
                l=mid;
163
        }
164
        fout<<x[tree.ask_version_diff(r)]<<'\n';
165
    }
166
  return 0;
167
}

可持久化并查集 #

给定 $n$ 个集合，第 $i$ 个集合内初始状态下只有一个数，为 $i$ 。

有 $m$ 次操作。操作分为 $3$ 种：

1 a b 合并 $a,b$ 所在集合；

2 k 回到第 $k$ 次操作（执行三种操作中的任意一种都记为一次操作）之后的状态；

3 a b 询问 $a,b$ 是否属于同一集合，如果是则输出 $1$ ，否则输出 $0$ 。

普通的并查集进行修改后，主要的区别就是fa数组。那就考虑对fa数组进行可持久化，朴素的思路是建可持久化线段树。但是并查集通常带了路径压缩，没法撤销，因此要使用按深度合并的并查集，保证每次都是 $\log$ 的。

因此直接用可持久化线段树或者说可持久化数组。单次修改，需要维护两个版本，一个是 $fa$ 的变化，一个是 $rank$ 的变化。

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
//#undef LOCAL_DEBUG
5
#ifdef LOCAL_DEBUG
6
#include "debug.h"
7
#else
8
#define debug(...) (void)0
9
#define debug_array(arr, len) (void)0
10
#endif
11

12
template <typename T>
13
class PersistentArray {
14
private:
15
    struct Node {
16
        T val;
17
        int l, r;
18
        int lson, rson;
19

20
        Node(T val = 0, int l = 0, int r = 0, int lson = -1, int rson = -1)
21
            : val(val), l(l), r(r), lson(lson), rson(rson) {}
22
    };
23

24
    vector<Node> nodes;
25
    vector<int> root;
26
    vector<T> data;
27

28
    int create(T val, int l, int r, int lson, int rson) {
29
        nodes.push_back({val, l, r, lson, rson});
30
        return nodes.size() - 1;
31
    }
32

33
    int build(int l, int r) {
34
        if (l == r) {
35
            return create(data[l], l, r, -1, -1);
36
        } else {
37
            int mid = (l + r) / 2;
38
            int left = build(l, mid);
39
            int right = build(mid + 1, r);
40
            return create(0, l, r, left, right);
41
        }
42
    }
43

44
    int revise_path(int u, int pos, const T val) {
45
        if (nodes[u].l == nodes[u].r) {
46
            int idx = create(val, nodes[u].l, nodes[u].r, -1, -1);
47
            return idx;
48
        } else {
49
            int lson = nodes[u].lson, rson = nodes[u].rson;
50
            int mid = (nodes[u].l + nodes[u].r) / 2;
51
            if (pos <= mid) {
52
                lson = revise_path(nodes[u].lson, pos, val);
53
            } else {
54
                rson = revise_path(nodes[u].rson, pos, val);
55
            }
56
            return create(nodes[u].val, nodes[u].l, nodes[u].r, lson, rson);
57
        }
58
    }
59

60
    T ask_path(int u, int pos) {
61
        if (nodes[u].l == nodes[u].r)
62
            return nodes[u].val;
63
        else {
64
            int mid = (nodes[u].l + nodes[u].r) / 2;
65
            if (pos <= mid)
66
                return ask_path(nodes[u].lson, pos);
67
            else
68
                return ask_path(nodes[u].rson, pos);
69
        }
70
    }
71

72
public:
73
    PersistentArray(vector<T> initData, int query_cnt = 0) {
74
        data = move(initData);
75
        nodes.reserve(data.size() * 4 + query_cnt * 8 * log2(data.size()));
76
        root.push_back(build(0, data.size() - 1));
77
    }
78

79
    int revise(int v, int pos, const T val) {
80
        int new_root = revise_path(root[v], pos, val);
81
        root.push_back(new_root);
82
        return root.size() - 1;
83
    }
84

85
    T ask(int v, int pos) {
86
        return ask_path(root[v], pos);
87
    }
88

89
    void copy(int v) {
90
        root.push_back(root[v]);
91
    }
92
};
93

94
struct PersistentDSU {
95
    PersistentArray<int> fa;  // 持久化数组
96
    PersistentArray<int> rank;
97

98
    PersistentDSU(int n, int q = 0): fa(init_array(n), q), rank(vector<int>(n,0), q) {
99

100
    }
101
    int find(int ver,int x){
102
        while (x!=fa.ask(ver,x))
103
            x=fa.ask(ver,x);
104
        return x;
105
    }
106
    void merge(int ver,int x,int y){    // 在版本ver的基础上合并x,y
107
        x=find(ver,x),y=find(ver,y);
108
        if (x==y){
109
            rank.copy(ver);
110
            fa.copy(ver);
111
            return ;
112
        }
113
        int rx=rank.ask(ver,x);
114
        int ry=rank.ask(ver,y);
115
        if (rx==ry)
116
            rank.revise(ver,y,ry+1);
117
        else
118
            rank.copy(ver);
119
        if (rx>ry)
120
            fa.revise(ver,y,x);
121
        else
122
            fa.revise(ver,x,y);
123
    }
124
    void copy(int ver){ // 复制一份版本ver
125
        rank.copy(ver);
126
        fa.copy(ver);
127
    }
128
private:
129
    static vector<int> init_array(int n){
130
        vector<int> data(n);
131
        iota(data.begin(),data.end(),0);
132
        return data;
133
    }
134
};
135

136
int main(){
137
  int n,q,op,k,a,b;
138
    cin>>n>>q;
139
    PersistentDSU dsu(n+1, q);
140
    for (int v=1;v<=q;v++){
141
        cin>>op;
142
        if (op==2){
143
            cin>>k;
144
            dsu.copy(k);
145
        }
146
        else{
147
            cin>>a>>b;
148
            if (op==1){
149
                dsu.merge(v-1,a,b);
150
            }
151
            else if (op==3){
152
            //    debug(a,b);
153
                a=dsu.find(v-1,a),b=dsu.find(v-1,b);
154
                cout<<(a==b)<<endl;
155
                dsu.copy(v-1);
156
            }
157
        }
158

159
    }
160
  return 0;
161
}

可持久化01Trie树#

acwing 256 最大异或和

要求 $l\leq p\le r$ ，使得 $(\oplus_{i=p}^n a[i])\oplus x$ 最大。实际上，对于从高到低每一位，肯定是能1就1，不能1就随便选了，反正是0。所以朴素的想法是，我们需要从高到低，假设总共8位，就从第8位开始，看看选哪些p可以使得为1，然后看第7位，看看我们之前选的那些p中，哪些可以使得第7位为1，一直到最后只有1个p，就是答案。

这样做就是01Tried树。

可持久化线段树#

可持久化数组#

静态区间第kkk小问题#

可持久化并查集#

可持久化01Trie树#

可持久化数组 #

静态区间第 $k$ 小问题 #

可持久化并查集 #