跳转至

可持久化 Trie

概述ψ(｀∇´)ψ

可持久化的的中心思想就是“函数式编程”。

也就是，在对数据结构的操作过程中，不会改变数据结构本身所具有的结构。

在需要修改某些信息时，不是直接修改，而是保留前一个版本的信息，并将数据创建一个副本，在副本上执行修改。

暴力的做法是每次修改信息的时候，都直接把整个数据结构复制一遍，在这个副本上修改。

但是空间的花费很明显是不能接受的。

发现每次修改只会修改一部分信息，那么单独将这部分信息创建一个副本，在这个副本上进行修改，就大大提高了空间利用率。

这样，数据结构就能很方便的保存所有历史版本的信息。

这种思想在可持久化线段树上体现更为明显，可持久化 Trie 其实也差不多。

应用ψ(｀∇´)ψ

可持久化 Trie 一般都是以 01 Trie 的方式出现。

01 Trie 可以支持一些全局查询，修改的操作。

但是无法很好的支持区间的操作。

比如，要多次询问某个序列 \(a\) 的 \([l,r]\) 中和 \(x\) 异或起来最大的一个数。

一般的 01 Trie 没法很方便的维护，只能对于每个询问单独建树。

或者是利用删除操作+类似莫队的离线思想优化，但这样的复杂度仍然很高。

可持久化 Trie 的思想就是，依次插入 \(a_1,a_2,a_3,\dots\)，然后保留每一次插入之后的版本 \(i\)。

并且第 \(i\) 个版本对应的根节点为 \(rt[i]\)。

它有一个很重要的性质：

从 \(rt[i]\) 出发所能访问到的所有节点构成的一棵 Trie 树，就是 \(a[1 \sim i]\) 全部插入之后形成的一棵 Trie 树。

利用这个性质，我们可以用前缀和的思想，把第 \(r\) 个版本构成的 Trie 和第 \(l - 1\) 个版本构成的 Trie “相减”，就得到了 \(a[l \sim r]\) 这部分插入之后得到的 Trie 树。

（注意，这里的“相减”并不是真正意义上的相减，具体实现方式看下方的 Query 操作）

实现ψ(｀∇´)ψ

插入ψ(｀∇´)ψ

可持久化 Trie 的数据保存方式和普通的 Trie 是一样的，都是利用字符指针指向含有信息的节点来保存数据。

介绍原理时仍然使用普通 Trie，代码实现使用 01 Trie。

仍然设 \(tr[p,ch]\) 表示 \(p\) 节点的 \(ch\) 字符指针，假设当前需要插入字符串 \(s\)，那么按照以下步骤即可：

  1. 设上一个版本的可持久化 Trie 对应的根节点为 \(rt\)，令一个指针 \(p = root\)，用一个指针 \(i\) 扫描 \(s\)。

  2. 新建一个节点 \(q\)，令新版本对应的根节点 \(rt\prime = q\)。

  3. 如果 \(p\not= \text{NULL}\)，将 \(p\) 的字符指针信息复制给 \(q\)。

具体来说，对于 \(\forall tr[p,ch] \not = \text{NULL}\)，令 \(tr[q,ch] = tr[p,ch]\)。

  1. 新建一个节点 \(q\prime\)，令 \(tr[q,s_i]\) 指向 \(q\prime\)，也就是说，\(p,q\) 两个节点除了编号以外的唯一区别，就是 \(s_i\) 这个字符指针指向的节点。

即是：\(tr[p,s_i]\not=tr[q,s_i]\)。

  1. 然后让 \(p,q\) 往下跳，\(p = tr[p,s_i],q = tr[q,s_i]\)，令 \(i + 1\)。

  2. 重复 \(3 \sim 5\)， 直到扫描完 \(s\)。

下图展示了在已经有历史版本 "bte" 的可持久化 Trie 中插入新的字符串 “kth” 的过程。

其中绿色节点为各个版本对应的根节点，红色节点为尾标记所处节点。

ptrie-1.gif

询问ψ(｀∇´)ψ

当我们需要查询某一段区间 \([l,r]\) 内和 \(x\) 异或起来最大的数时，应当怎么处理？

上面已经说了，利用前缀相减的思想，用两个维护前缀 \(1\sim r,1\sim l-1\) 的两个版本的 Trie 相减得到 \([l,r]\) 对应的 Trie。

但是我们并不能直接相减，因为并不存在一种让 Trie 和 Trie 之间做减法的操作。

首先根据可持久化 Trie 的性质，从 \(rt[i]\) 出发能访问到的节点构成了第 \(i\) 个版本的 Trie。

所以可以先从 \(r\) 出发，这样就满足了 \(r\) 的上界限制。

怎么满足 \(l - 1\) 的下界限制呢？

我们可以利用在节点上保存的附加信息。

设 \(end[p]\) 表示以 \(p\) 为尾节点的数是序列里的第几个数（可以当作“版本”看待）。

设 \(las[p]\) 表示以 \(p\) 为根的子树中 \(end\) 的最大值。

那么我们递归访问节点的时候，只需要考虑 \(las \ge l - 1\) 的节点即可。

因为 \(las\) 也可以看作：这颗子树最后被哪一个版本所更新过。

递归下去就可以了。

代码ψ(｀∇´)ψ

President-01Trie 
 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
const int si = 1e4 + 10;
const int MaxDepth = 21;
// 可以不用强制位数都一样
// 写了也可以。

int s[si];
int tr[si * (MaxDepth + 1)][2];
int las[si * (MaxDepth + 1)];
int tot = 0, root[si];

// 当前版本，当前位数，p, q 
void insert(int i, int k, int p, int q) {
    if(k < 0) {
        las[q] = i;
        return;
    }
    int ch = s[i] >> k & 1;
    if(p) 
        tr[q][ch ^ 1] = tr[p][ch ^ 1];
    // p 非空，复制节点信息。
    tr[q][ch] = ++tot;
    // p 和 q 的 ch 指针应当不一样。
    insert(i, k - 1, tr[p][ch], tr[q][ch]);
    las[q] = max(las[tr[q][0]], las[tr[q][1]]);
}

// 查询 [l, r] 中和 val 异或起来最大的数。
// 调用时需要 ask(root[r], MaxDepth, val, l - 1)
// 因为可持久化 Trie 的root[i] 能访问到的元素只有 s[1 ~ i]。
// 而只考虑 las >= l - 1 的节点则能满足下界。
int ask(int p, int k, int val, int limit) {
    if(k < 0)
        return s[las[p]];
    int ch = val >> k & 1;
    if(las[tr[p][ch ^ 1]] >= limit)
        return ask(tr[p][ch ^ 1], k - 1, val, limit);
    else 
        return ask(tr[p][ch], k - 1, val, limit);
    // 走不了 1 指针，所以只能往 0 指针走。
}

int main() {
    s[0] = 0, las[0] = -1, root[0] = ++tot;
    insert(0, MaxDepth, 0, root[0]);
    // 这几句话是必须的，因为你要保证对于任意 l \in [1, n], 都有一个 l - 1 存在。
}

当然，可持久化 Trie 的应用不止这些，可以考虑配合维护异或和的 01Trie，实现动态插入，删除指定元素，查询区间异或和的操作。

TODO：之后写一个这样的 可持久化 Trie，然后用暴力对拍验证正确性。

参考资料：《算法竞赛进阶指南》，OI - Wiki

最后更新: May 9, 2023