Zth's Blog

记录学习路上的点滴

0%

可持久化数据结构

发表于 更新于 分类于

可持久化Trie和可持久化线段树

可持久化

每次加入新的数据时， 从当前根节点可以去到之前的节点， 但是不能反向操作， 这也是为什么Ex_Trie每次添加的新字符串一定都是新开的， 不能用之前的

Ex_Trie

思路

同上

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>

int root[100005], rs;
int trie[100005][31], tot = 1;
bool end[100005];

void Insert(char* s)
{
    int p = root[rs];

    rs ++;
    root[rs] = ++ tot;

    int len = strlen(s), q = tot;

    for(int i = 0; i < len; i ++)
    {
        if(p)
            for(int j = 0; j < 26; j ++)
                trie[q][j] = trie[p][j]; // 继承之前的

        int ch = s[i] - 'a';
        trie[q][ch] = ++ tot; // 自己新的一定要新开节点
        
        q = trie[q][ch];
        p = trie[p][ch];
    }

    end[q] = true;
}

bool Search(char *s, int rt) // rt为版本
{
    int len = strlen(s), p = root[rt];

    for(int i = 0; i < len; i ++)
    {
        int ch = s[i] - 'a';

        p = trie[p][ch];

        if(!p) return false;
    }

    return end[p];
}

int main()
{

}

EX_Segment_Tree

思路

见《算法竞赛进阶指南》

只有单点修改， 标记永久化还没学

代码

题目为洛谷模板题P3919 【模板】可持久化线段树 1（可持久化数组）

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
#include <iostream>
#include <cstdio>

int n, m;
int a[1000006];
int tot;
struct SegmentTree
{
    int dat;
    int lc, rc;
} tree[80000007];
int ver[1000006], vs;

int Build(int l, int r)
{
    int p = ++ tot;
    
    if(l == r) {tree[p].dat = a[l]; return p;}
    
    int mid = (l + r) >> 1;
    
    tree[p].lc = Build(l, mid);
    tree[p].rc = Build(mid + 1, r);
    
    return p;
}

int Modify(int now, int l, int r, int pos, int val)
{
    int p = ++ tot;
    
    tree[p] = tree[now];
    
    if(l == r) {tree[p].dat = val; return p;}
    
    int mid = (l + r) >> 1;
    
    if(pos <= mid)
        tree[p].lc = Modify(tree[now].lc, l, mid, pos, val);
    else
        tree[p].rc = Modify(tree[now].rc, mid + 1, r, pos, val);
    
    return p;
}

int Query(int now, int l, int r, int pos)
{
    if(l == r) return tree[now].dat;
    
    int mid = (l + r) >> 1;
    
    if(pos <= mid)
        return Query(tree[now].lc, l, mid, pos);
    else
        return Query(tree[now].rc, mid + 1, r, pos);
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    
    ver[vs] = Build(1, n);
    
    for(int i = 1; i <= m; i ++)
    {
        int vi, op;
        scanf("%d%d", &vi, &op);
        
        if(op == 1)
        {
            int pi, val;
            scanf("%d%d", &pi, &val);
            
            vs ++;
            ver[vs] = Modify(ver[vi], 1, n, pi, val);
        }
        else
        {
            int pi;
            scanf("%d", &pi);
            
            int res = Query(ver[vi], 1, n, pi);
            printf("%d\n", res);
            
            vs ++;
            ver[vs] = Modify(ver[vi], 1, n, pi, res);
        }
    }
    
    return 0;
}