一、寫時拷貝與可持久化數據結構的區別
寫時拷貝與可持久化數據結構的區別是可持久化:將數據結構的所有歷史版本記錄下來,稱為可持久化。不是所有的數據結構都是可以持久化的,可持久化的數據結構要求其結構穩定,比如堆(是一顆滿二叉樹,結構穩定)、樹狀數組、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,步直到建樹完成。