一、寫時拷貝與可持久化數據結構的區(qū)別

寫時拷貝與可持久化數據結構的區(qū)別是可持久化：將數據結構的所有歷史版本記錄下來，稱為可持久化。不是所有的數據結構都是可以持久化的，可持久化的數據結構要求其結構穩(wěn)定，比如堆（是一顆滿二叉樹，結構穩(wěn)定）、樹狀數組、trie（字典樹）、線段樹等。平衡樹就不可以進行持久化操作，因為其存在左旋、右旋的操作。

存下來所有的歷史版本有兩種方式，一種是每改動一次則全部備份下來；另一種是增量備份。名列前茅種方式時空復雜度都比較高，不使用這種方式，我們這里只講解增量備份的方式（類似于git）。

增量備份的核心思想是：只記錄每個版本與前一個版本不同的部分。

可持久化Trie的用途：

正常的Trie樹可以解決字符串的一些問題，特殊的Trie樹（比如0/1Trie）可以解決最大異或和的相關問題，但是如果每次的詢問是針對區(qū)間的，Trie樹就不好解決，因為你不能對每個區(qū)間都建一棵Trie樹，那樣空間就會爆炸，于是，我們的可持久化Trie就登場了。

延伸閱讀：

二、可持久化Trie的構造

設trie[x][ch]，表示從x號節(jié)點連向的字符為ch的點的編號（與普通Trie的含義相同），root[i]表示第i次插入的字符串的根節(jié)點，tot代表總節(jié)點數

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

1：首先新建第i個字符串的根節(jié)點，并定義兩個變量p，q代表當前串的節(jié)點和上一個版本與之對應的節(jié)點，初始化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，步直到建樹完成。