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

ACM
12k words

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

可持久化线段树

可持久化数组

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

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

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

朴素的实现肯定是爆时间空间的。考虑有什么方法维护，可持久化线段树可以维护。对于线段树，单次修改实际上只修改了一个长度为log⁡n\log n的路径。那我们重新建树就行了，每次的新树，继承了前一个版本的树的剩余节点，新增的节点只有log⁡n\log 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
template<typename T>
class PersistentArray {
private:
    struct Node {
        T val;
        int l, r;
        int lson, rson;
    };

    vector<Node> node;
    vector<int> root;
    vector<T> data;

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

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

    /* 建立持久化数组的初始版本 */
    int build(int l, int r) {
        if (l == r)
            return create(data[l], l, r, -1, -1);
        else {
            int mid = (l + r) / 2;
            int lson = build(l, mid);
            int rson = build(mid + 1, r);
            return create(0, l, r, lson, rson);
        }
    }

    /* 修改持久化数组路径 */ 
    int revise_path(int u, int pos, const T val) {
        int p = clone(u);
        if (node[u].l == node[u].r) 
            node[p].val = val;
        else {
            int mid = (node[u].l + node[u].r) / 2;
            if (pos <= mid)
                node[p].lson = revise_path(node[u].lson, pos, val);
            else
                node[p].rson = revise_path(node[u].rson, pos, val);
        }
        return p;
    }

    /* 查询持久化数组的某个版本的值 */
    T ask_path(int u, int pos) {
        if (node[u].l == node[u].r)
            return node[u].val;
        else {
            int mid = (node[u].l + node[u].r) / 2;
            if (pos <= mid)
                return ask_path(node[u].lson, pos);
            else 
                return ask_path(node[u].rson, pos);
        }
    }

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

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

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

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

静态区间第kk小问题

前置：权值线段树

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

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

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

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

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

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

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

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
161
162
163
164
165
166
167
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5;

int n,q;

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

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

    int create(int val,T l,T r,int lson,int rson) {
        node.push_back({val,l,r,lson,rson});
        return node.size()-1;
    }
    int clone(int u){
        node.push_back(node[u]);
        return node.size()-1;
    }
    /* 建树，区间[l,r] */
    int build(T l,T r) {
        if (l==r)
            return create(0,l,r,-1,-1);
        else {
            T mid=(l+r)/2;
            return create(0,l,r,build(l,mid),build(mid+1,r));
        }
    }
    
    /* 对val值的所有路径节点修改x */
    void revise(T val,int x){
        int u=version.back().root;  // 默认从最后一个版本开始修改
        int *fa=nullptr;
        while (true){
            int v=clone(u);
            if (fa)
                *fa=v;
            else
                version.push_back(Version{v,val,x});
            node[v].cnt+=x;
            if (node[u].l==node[u].r)
                return ;
            T mid=(node[u].l+node[u].r)/2;
            u=(val<=mid)?node[u].lson:node[u].rson;
            fa=(val<=mid)?(&node[v].lson):(&node[v].rson);
        }
    }
    /* 查询区间权值 */
    int ask_range(int u,const T l,const T r){
        if (l<=node[u].l&&node[u].r<=r)
            return node[u].cnt;
        T mid=(node[u].l+node[u].r)/2;
        int ret=0;
        if (l<=mid)
            ret+=ask_range(node[u].lson,l,r);
        if (r>mid)
            ret+=ask_range(node[u].rson,l,r);
        return ret;
    }

public:
    CountSegmentTree(T l, T r){ 
        // 传入开的桶的范围，[L,R]
        node.reserve((r-l+5)*32);
        version.push_back(Version{build(l,r),0});
    }
    /* 插入值val，返回版本号 */
    int insert(T val){
        revise(val,1);
        return version.size()-1;
    }
    /* 删除值val，返回版本号 */
    void remove(T val){
        revise(val,-1);
        return version.size()-1;
    }
    /* 查询版本[L,R]的数的个数 */
    int ask_cnt(int ver, T l, T r){
        return ask_range(version[ver].root,l,r);
    }
    /* 查询版本[L,R]修改权值的数 */
    T ask_version_diff(int ver){
        return version[ver].revise_val;
    }
};

namespace fastio
{
    const int bufl=1<<16;
    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};
    const double base2[16]={1,1e1,1e2,1e3,1e4,1e5,1e6,1e7,1e8,1e9,1e10,1e11,1e12,1e13,1e14,1e15};
    struct IN{
        FILE *IT;char ibuf[bufl],*is=ibuf,*it=ibuf;
        IN(){IT=stdin;}IN(char *a){IT=fopen(a,"r");}
        inline char getChar(){if(is==it){it=(is=ibuf)+fread(ibuf,1,bufl,IT);if(is==it)return EOF;}return *is++;}
        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;}
        IN& operator>>(char &a){a=getChar();return *this;}
        IN& operator>>(char *a){do{*a=getChar();}while(*a<=32);while(*a>32)*++a=getChar();*a=0;return *this;}
        IN& operator>>(string &a){char b=getChar();while(b<=32)b=getChar();while(b>32)a+=b,b=getChar();return *this;}
        IN& operator>>(int &a){getInt(a);return *this;}
        IN& operator>>(long long &a){getInt(a);return *this;}
    };
    struct OUT{
        FILE *IT;char obuf[bufl],*os=obuf,*ot=obuf+bufl;int Eps;long double Acc;
        OUT(){IT=stdout,Eps=6,Acc=1e-6;}OUT(char *a){IT=fopen(a,"w"),Eps=6,Acc=1e-6;}
        inline void ChangEps(int x=6){Eps=x;}
        inline void flush(){fwrite(obuf,1,os-obuf,IT);os=obuf;}
        inline void putChar(int a){*os++=a;if(os==ot)flush();}
        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);}
        OUT& operator<<(char a){putChar(a);return *this;}
        OUT& operator<<(char *a){while(*a>32)putChar(*a++);return *this;}
        OUT& operator<<(string a){for(auto c:a)putChar(c);return *this;}
        OUT& operator<<(int a){putInt(a);return *this;}
        OUT& operator<<(long long a){putInt(a);return *this;}
        ~OUT(){flush();}
    };
}
using fastio::IN;
using fastio::OUT;
IN fin;
OUT fout;

int main(){
//	freopen("P3834_9.in","r",stdin);
//	freopen("P3834_9.txt","w",stdout);
	fin>>n>>q;
    typedef pair<int,int> P;
    vector<int> x(n+1);
    vector<P> a(n);
    for (int i=0;i<n;i++){
    	fin>>a[i].first;
        a[i].second=i+1;
        x[i+1]=a[i].first;
    }
    sort(a.begin(),a.end());
    CountSegmentTree<int> tree(1,n);
    for (P p: a)
        tree.insert(p.second);
    int L,R,k;
    int l,r,mid;
    while (q--){
    	fin>>L>>R>>k;
        l=0,r=n;
        while (r-l>1){
            mid=(l+r)>>1;
            if (tree.ask_cnt(mid,L,R)>=k)
                r=mid;
            else
                l=mid;
        }
        fout<<x[tree.ask_version_diff(r)]<<'\n';
    }
	return 0;
}

可持久化并查集

给定 nn 个集合，第 ii 个集合内初始状态下只有一个数，为 ii。

有 mm 次操作。操作分为 33 种：

  • 1 a b 合并 a,ba,b 所在集合；
  • 2 k 回到第 kk 次操作（执行三种操作中的任意一种都记为一次操作）之后的状态；
  • 3 a b 询问 a,ba,b 是否属于同一集合，如果是则输出 11，否则输出 00。

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

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

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
161
#include <bits/stdc++.h>
using namespace std;

//#undef LOCAL_DEBUG
#ifdef LOCAL_DEBUG
#include "debug.h"
#else
#define debug(...) (void)0
#define debug_array(arr, len) (void)0
#endif

template <typename T>
class PersistentArray {
private:
    struct Node {
        T val;
        int l, r;
        int lson, rson; 

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

    vector<Node> nodes; 
    vector<int> root;  
    vector<T> data;

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

    int build(int l, int r) {
        if (l == r) {
            return create(data[l], l, r, -1, -1);
        } else {
            int mid = (l + r) / 2;
            int left = build(l, mid);
            int right = build(mid + 1, r);
            return create(0, l, r, left, right);
        }
    }

    int revise_path(int u, int pos, const T val) {
        if (nodes[u].l == nodes[u].r) {
            int idx = create(val, nodes[u].l, nodes[u].r, -1, -1);
            return idx;
        } else {
            int lson = nodes[u].lson, rson = nodes[u].rson;
            int mid = (nodes[u].l + nodes[u].r) / 2;
            if (pos <= mid) {
                lson = revise_path(nodes[u].lson, pos, val);
            } else {
                rson = revise_path(nodes[u].rson, pos, val);
            }
            return create(nodes[u].val, nodes[u].l, nodes[u].r, lson, rson);
        }
    }

    T ask_path(int u, int pos) {
        if (nodes[u].l == nodes[u].r)
            return nodes[u].val;
        else {
            int mid = (nodes[u].l + nodes[u].r) / 2;
            if (pos <= mid)
                return ask_path(nodes[u].lson, pos);
            else
                return ask_path(nodes[u].rson, pos);
        }
    }

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

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

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

    void copy(int v) {
        root.push_back(root[v]);
    }
};

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

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

    }
    int find(int ver,int x){
        while (x!=fa.ask(ver,x))
            x=fa.ask(ver,x);
        return x;
    }
    void merge(int ver,int x,int y){    // 在版本ver的基础上合并x,y
        x=find(ver,x),y=find(ver,y);
        if (x==y){
            rank.copy(ver);
            fa.copy(ver);
            return ;
        }
        int rx=rank.ask(ver,x);
        int ry=rank.ask(ver,y);
        if (rx==ry)
            rank.revise(ver,y,ry+1);
        else
            rank.copy(ver);
        if (rx>ry)
            fa.revise(ver,y,x);
        else
            fa.revise(ver,x,y);
    }
    void copy(int ver){ // 复制一份版本ver
        rank.copy(ver);
        fa.copy(ver);
    }
private:
    static vector<int> init_array(int n){
        vector<int> data(n);
        iota(data.begin(),data.end(),0);
        return data;
    }
};

int main(){
	int n,q,op,k,a,b;
    cin>>n>>q;
    PersistentDSU dsu(n+1, q);
    for (int v=1;v<=q;v++){
        cin>>op;
        if (op==2){
            cin>>k;
            dsu.copy(k);
        }
        else{
            cin>>a>>b;
            if (op==1){
                dsu.merge(v-1,a,b);
            }
            else if (op==3){
            //    debug(a,b);
                a=dsu.find(v-1,a),b=dsu.find(v-1,b);
                cout<<(a==b)<<endl;
                dsu.copy(v-1);
            }
        }

    }
	return 0;
}

可持久化01Trie树

acwing 256 最大异或和

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

这样做就是01Tried树。