图的遍历算法及应用（可持久化Trie与线段树的原理以及实现）

图的遍历算法及应用（可持久化Trie与线段树的原理以及实现）有方法，我们只需要记录修改过的Trie的关键路径就好了。其次我们注意到在上面那张链表图中进入下一个节点的时候，每次都要判断有没有我们要进入的新版本的分支，十分麻烦。有没有方法可以保证我们向下找的节点全部是我们要的版本呢？下面以链表为例新的版本是部分建立在老的版本之上的。不变的地方不变，有编号的地方就加入新版本的分支。基于版本分支的思想，我们怎么建立一个可持久化Trie呢？

引言

当我们需要保存一个数据结构不同时间的每个版本 最朴素的方法就是每个时间都创建一个独立的数据结构 单独储存。

但是这种方法不仅每次复制新的数据结构需要时间，空间上也受不了储存这么多版本的数据结构。

然而有一种叫git的工具，可以维护工程代码的各个版本，而空间上也不至于十分爆炸。怎么做到呢？

答案是版本分支，即每次创建新的版本不完全复制老的数据结构，而是在老的数据结构上加入不同版本的分支。

下面以链表为例

新的版本是部分建立在老的版本之上的。不变的地方不变，有编号的地方就加入新版本的分支。

实现可持久化Trie

基于版本分支的思想，我们怎么建立一个可持久化Trie呢？

其次我们注意到在上面那张链表图中进入下一个节点的时候，每次都要判断有没有我们要进入的新版本的分支，十分麻烦。有没有方法可以保证我们向下找的节点全部是我们要的版本呢？

有方法，我们只需要记录修改过的Trie的关键路径就好了。

什么叫关键路径呢？

这里先假设我们只修改Trie上的一个节点。而所谓关键路径就是从Trie的根节点到修改节点的路径，我们只创建这路径上的节点，其余节点全部继承一个老版本的节点。

如图

这是一个向有{cat map}的Trie里插入mark的新单词的例子。

不难发现，在ROOT_NEW可以到达的节点构成的树中，凡是不在mark这个单词的路径上的节点统统用的是老版本树的节点。

代码实现

代码很简单，就不多做解释了

#include <iostream> #include <string> using namespace std; const int N = 1e1 128; int his[128]; int h; int to[N][26]; int p; void insert(string &s) { int old = p; //老树的节点 his[ h] = p; int now = p; //新树的 for (auto i : s) { for (int j = 0; j < 26; j ) if (i - 'A' != j) //非关键路径上的节点继承老树 to[now][j] = to[old][j]; to[now][i - 'A'] = p; //关键路径上的节点就新建 now = p; old = to[now][i - 'A']; //老树也要跟下去 } return; } bool ask(int h string &s) //询问某个版本的Trie里 是否有对应的单词 { int now = his[h]; for (auto i : s) { if (to[now][i - 'A'] == 0) return false; now = to[now][i - 'A']; } return true; } int main() { int opt; while (cin >> opt) { if (opt == 1) //插入 { string str; cin >> str; insert(str); } else { string str; int h; cin >> str >> h; cout << ((ask(h str)) ? 'Y' : 'N') << endl; } } return 0; }可持久化线段树

终于到了我们的主题了。可持久化线段树顾名思义就是可持久化的线段树

存在的意义首先是满足部分线段树的要求，然后也能根据线段树的特性解决一部分可持久化Trie的弊端。

聪明的小伙伴可以发现在一个Trie中，我们要把一条完整的子链完全复制下来，如果我们老版本的Trie本来就是一条链，这种操作无异于把Trie重新复制一遍，还是相当慢，怎么办？

在维护一个Trie的时候，这种问题可能会让人头疼。但是线段树可以完全避免，因为线段树的树高是完全有限的[Log(n)Log(n)级别]。

基本思路还是只记录修改过的关键路径，不在关键路径上的节点继承老版本的子树。

基本原理还是和可持久化Trie差不多，看图和代码基本也能理解了

代码实现

有一点要注意的是 这个线段树的节点关系已经是一个有向图了 不能用满二叉树的性质去计算他的左右儿子。需要手动记录。

其实就是P3919 【模板】可持久化线段树 1（可持久化数组）的题解

#include <iostream> using namespace std; const int N = 5e7 128; int num[N / 10]; int his[N / 10]; int h_ptr; int lc[N] rc[N] val[N]; int p; int n m; void build(int u int l int r) //和常规的线段树建立差不多 就是要左右儿子不能用满二叉树性质算出来了 所以要手动存 { if (l == r) { val[u] = num[l]; return; } lc[u] = p; rc[u] = p; int mid = (l r) >> 1; build(lc[u] l mid); build(rc[u] mid 1 r); } void fork_only(int h) //仅仅只复制一个历史版本 { his[h_ptr ] = his[h]; } void fork_and_edit(int h int addr int val_) //复制一个带修改的版本为h的历史版本到最新版本中(把addr这里的数修改为val) { int old = his[h]; int now = p; his[h_ptr ] = p; int l = 1 r = n; while (l < r) { int mid = (l r) >> 1; if (addr <= mid) //关键路径在左儿子 { rc[now] = rc[old]; //所以右儿子直接继承 lc[now] = p; //新建一个左儿子 now = lc[now]; old = lc[old]; r = mid; } else { lc[now] = lc[old]; //反之继承左儿子 rc[now] = p; now = rc[now]; old = rc[old]; l = mid 1; } } val[now] = val_; return; } int query(int u int addr) { int l = 1 r = n; while (l < r) { int mid = (l r) >> 1; if (addr <= mid) u = lc[u] r = mid; else u = rc[u] l = mid 1; } return val[u]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n >> m; for (int i = 1; i <= n; i ) cin >> num[i]; his[h_ptr ] = p; build(p 1 n); for (int i = 1; i <= m; i ) { int v opt loc; cin >> v >> opt >> loc; if (opt == 1) { int value; cin >> value; fork_and_edit(v loc value); } else { cout << query(his[v] loc) << endl; fork_only(v); } } return 0; }

作者： Ice

链接： https://www.cnblogs.com/Icys/p/Persistence_SegmentTree.html