一、寫(xiě)時(shí)拷貝與可持久化數(shù)據(jù)結(jié)構(gòu)的區(qū)別

寫(xiě)時(shí)拷貝與可持久化數(shù)據(jù)結(jié)構(gòu)的區(qū)別是可持久化：將數(shù)據(jù)結(jié)構(gòu)的所有歷史版本記錄下來(lái)，稱為可持久化。不是所有的數(shù)據(jù)結(jié)構(gòu)都是可以持久化的，可持久化的數(shù)據(jù)結(jié)構(gòu)要求其結(jié)構(gòu)穩(wěn)定，比如堆（是一顆滿二叉樹(shù)，結(jié)構(gòu)穩(wěn)定）、樹(shù)狀數(shù)組、trie（字典樹(shù)）、線段樹(shù)等。平衡樹(shù)就不可以進(jìn)行持久化操作，因?yàn)槠浯嬖谧笮?、右旋的操作?/p>

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

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

可持久化Trie的用途：

正常的Trie樹(shù)可以解決字符串的一些問(wèn)題，特殊的Trie樹(shù)（比如0/1Trie）可以解決最大異或和的相關(guān)問(wèn)題，但是如果每次的詢問(wèn)是針對(duì)區(qū)間的，Trie樹(shù)就不好解決，因?yàn)槟悴荒軐?duì)每個(gè)區(qū)間都建一棵Trie樹(shù)，那樣空間就會(huì)爆炸，于是，我們的可持久化Trie就登場(chǎng)了。

延伸閱讀：

二、可持久化Trie的構(gòu)造

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

可持久化Trie插入第i個(gè)字符串的構(gòu)造流程如下：

1：首先新建第i個(gè)字符串的根節(jié)點(diǎn)，并定義兩個(gè)變量p，q代表當(dāng)前串的節(jié)點(diǎn)和上一個(gè)版本與之對(duì)應(yīng)的節(jié)點(diǎn)，初始化p=root[i-1]，q=root[i]

2：若當(dāng)前字符串的下一個(gè)字符是ch，那么就讓trie[q][ch]=++tot;

然后對(duì)于不是ch的字符CH，trie[q][CH]=trie[p][CH];

3:讓p=trie[p][ch],q=trie[q][ch],并重復(fù)2,3，步直到建樹(shù)完成。