一、寫時拷貝與可持久化數(shù)據(jù)結(jié)構(gòu)的區(qū)別
寫時拷貝與可持久化數(shù)據(jù)結(jié)構(gòu)的區(qū)別是可持久化:將數(shù)據(jù)結(jié)構(gòu)的所有歷史版本記錄下來,稱為可持久化。不是所有的數(shù)據(jù)結(jié)構(gòu)都是可以持久化的,可持久化的數(shù)據(jù)結(jié)構(gòu)要求其結(jié)構(gòu)穩(wěn)定,比如堆(是一顆滿二叉樹,結(jié)構(gòu)穩(wěn)定)、樹狀數(shù)組、trie(字典樹)、線段樹等。平衡樹就不可以進行持久化操作,因為其存在左旋、右旋的操作。
存下來所有的歷史版本有兩種方式,一種是每改動一次則全部備份下來;另一種是增量備份。名列前茅種方式時空復(fù)雜度都比較高,不使用這種方式,我們這里只講解增量備份的方式(類似于git)。
增量備份的核心思想是:只記錄每個版本與前一個版本不同的部分。
可持久化Trie的用途:
正常的Trie樹可以解決字符串的一些問題,特殊的Trie樹(比如0/1Trie)可以解決最大異或和的相關(guān)問題,但是如果每次的詢問是針對區(qū)間的,Trie樹就不好解決,因為你不能對每個區(qū)間都建一棵Trie樹,那樣空間就會爆炸,于是,我們的可持久化Trie就登場了。
延伸閱讀:
二、可持久化Trie的構(gòu)造
設(shè)trie[x][ch],表示從x號節(jié)點連向的字符為ch的點的編號(與普通Trie的含義相同),root[i]表示第i次插入的字符串的根節(jié)點,tot代表總節(jié)點數(shù)
可持久化Trie插入第i個字符串的構(gòu)造流程如下:
1:首先新建第i個字符串的根節(jié)點,并定義兩個變量p,q代表當(dāng)前串的節(jié)點和上一個版本與之對應(yīng)的節(jié)點,初始化p=root[i-1],q=root[i]
2:若當(dāng)前字符串的下一個字符是ch,那么就讓trie[q][ch]=++tot;
然后對于不是ch的字符CH,trie[q][CH]=trie[p][CH];
3:讓p=trie[p][ch],q=trie[q][ch],并重復(fù)2,3,步直到建樹完成。