可持久化数据结构
可持久化原理，可持久化Trie，可持久化线段树（主席树）。
可持久化数据结构
一个数据结构可持久化的条件是：该数据结构在操作的时候不会发生拓扑结构的变化。
可持久化数据结构能解决的问题：记录该数据结构的历史版本，支持对历史版本的操作。
可持久化数据结构的原理：只记录某个版本和前一个版本不一样的地方。如果该数据结构每次改变的结点很少，那么前面提到的记录方法的效率就会很高。
可持久化Trie
构建
创建一棵空树，代表第 0 个版本。
插入
以插入字符串为例子：
-
首先，需要开一个新的结点，表示新版本的根，假设当前是第
i个版本，那么就是root[i] = ++idx。 -
上一个版本的根结点显然是
root[i - 1]，不妨用p表示我们在版本i - 1上走过的结点的id，q表示我们在版本i上走过的结点的id。 -
假如
p不为空，那么需要先把p结点的所有儿子赋值给q的对应的儿子，然后把字符串当前位置代表的指针修改了，指向一个新开的结点；如果p为空，那么就直接把字符串当前位置表示的边指向一个新开的结点即可。然后p = trie[p][ch]，q = trie[q][ch]，其中ch表示当前字符串的字符表示的边。这里注意一个细节，如果
p为空，那么在我们实现时当然会有所有的trie[p][ch] = 0，所以往下走的时候p一定一直都是空，所以就一直不会发生复制的情况，保证了复杂度。 -
走到字符串的尽头，就可以结束了。
如果需要在插入的过程中需要同时刷新以每个结点为根的子树的信息，可能需要使用递归插入的形式实现来保证先更新子树再更新根（不同于之前的一个循环跑下来就完成插入）。