一、写时拷贝与可持久化数据结构的区别

写时拷贝与可持久化数据结构的区别是可持久化：将数据结构的所有历史版本记录下来，称为可持久化。不是所有的数据结构都是可以持久化的，可持久化的数据结构要求其结构稳定，比如堆（是一颗满二叉树，结构稳定）、树状数组、trie（字典树）、线段树等。平衡树就不可以进行持久化操作，因为其存在左旋、右旋的操作。

存下来所有的历史版本有两种方式，一种是每改动一次则全部备份下来；另一种是增量备份。名列前茅种方式时空复杂度都比较高，不使用这种方式，我们这里只讲解增量备份的方式（类似于git）。

增量备份的核心思想是：只记录每个版本与前一个版本不同的部分。

可持久化Trie的用途：

正常的Trie树可以解决字符串的一些问题，特殊的Trie树（比如0/1Trie）可以解决最大异或和的相关问题，但是如果每次的询问是针对区间的，Trie树就不好解决，因为你不能对每个区间都建一棵Trie树，那样空间就会爆炸，于是，我们的可持久化Trie就登场了。

延伸阅读：

二、可持久化Trie的构造

设trie[x][ch]，表示从x号节点连向的字符为ch的点的编号（与普通Trie的含义相同），root[i]表示第i次插入的字符串的根节点，tot代表总节点数

可持久化Trie插入第i个字符串的构造流程如下：

1：首先新建第i个字符串的根节点，并定义两个变量p，q代表当前串的节点和上一个版本与之对应的节点，初始化p=root[i-1]，q=root[i]

2：若当前字符串的下一个字符是ch，那么就让trie[q][ch]=++tot;

然后对于不是ch的字符CH，trie[q][CH]=trie[p][CH];

3:让p=trie[p][ch],q=trie[q][ch],并重复2,3，步直到建树完成。

上一篇

leetcode为什么提示列表没有len()?

下一篇

数据结构中的算法设计题需要写哪些步骤?