算法 {Trie字典树}
@LOC: 1
T
r
i
e
樹
Trie樹
Trie樹是一顆K叉的有根樹, 即每個點 都有K個兒子 且這些兒子都是有次序的, 任何一條邊fa->son的值 等於son是fa的第幾個兒子 因此邊的值為[0,K);
任何一個點 他代表: 從根節點root到當前點的邊的序列, 比如某點cur的序列是[0123]表明: 從根節點 到達第0個兒子 然後到達第1個兒子 然後到達第2個兒子 然後到達第3個兒子 就到達了cur點;
. 因此 TRIE樹是用來存儲字符串/前綴的, 比如小寫字符串 他可以用一個26叉的TRIE樹來存儲 "abcd"他對應於[0123] (比如假設TRIE樹中D點=[0123], C點=[012]) 那麼 這個字符串"abcd"就對應TRIE樹中的D點 他的前綴"abc"就對應C點;
#動態開點#
前言: 以
K
=
2
K=2
K=2叉的TRIE樹為例, 此時如果你想存儲一個長度=60的字符串, 那麼這個樹的大小 就是2^60就爆空間了; 對於K更大 長度更長的字符串 就更不可能了; 而對於一個長度為N的字符串 他對應到TRIE樹中 他只會使用N+1個點 並不會訪問整個TRIE樹;
. 因此 TRIE樹不能像樸素的K叉樹那樣預存儲, 而是使用的是動態開點;
TRIE樹 從結構上講 他就是個K叉樹, 但是 它裡面的很多節點 是虛的(還未開闢的狀態) 可以想象下 一個K叉樹 有些點是亮的 其他點都是暗的(表示還未使用), 當插入字符串(長度為N)時 他會依次的訪問N+1個點 如果某個點是暗的 那麼就臨時開啟他;
字典樹 又稱為字符串前綴樹, 所謂前綴 即他存儲的信息 一定是父節點的信息 而不是子節點 , 線段樹存儲的信息 是子節點的信息 而不是父節點信息;
也就是 TRIE的遍歷方式 一般都是FOR循環 而不是DFS遞歸, 因為當前節點信息的更新 不需要用到兒子信息;
. 你可能認為 那我就是要讓他存儲兒子信息不行嗎? 也就是後綴樹; 首先如果後綴樹 那你統一將所有原始字符串reverse掉 不就變成了前綴樹; 如果你非要存儲子節點信息, 比如初始字符串為[abcZZ, bbcZZ, aacZZ], 令"abc"對應的節點為x, 那麼假如你要存儲兒子信息 那麼x的信息就是abc, abcZ, abcZZ, 你是無法存儲cZZ這個後綴的, 因為當前節點x 他表示的就是abc, 如果你要讓x存儲兒子信息 他的信息只能限制於是所有以abc為前綴的字符串, 你是無法脫離開這個前綴的;
當然 除非你對x節點的信息的需要 就是(所有以abc為前綴的字符串集合裡)的信息, 那麼你當然可以這樣定義 那麼TRIE的遍歷 就要改成遞歸形式了;
也就是 比如"abc"這個字符串 對應於TRIE樹中的x這個節點, 那麼 比如你TRIE維護的字符串集合為S, 則S中 所有的以"abc"為前綴的字符串 他都一定經過x這個節點, 也就是 任意形如"abc???"的字符串 他的這個"abc"前綴 所對應在TRIE中的節點 就是x; 因此 僅用一個x節點 就可以統一的表示 S中所有的以"abc"為前綴的字符串, 即TRIE本身就是前綴樹, 因此節點的信息 通常維護的是有關前綴的信息;
@DELI;
給定一個節點X, 那麼該節點 其所對應的字符串 就是唯一確定的;
這是因為 有根樹上的任意節點 其父節點一定是唯一的, 因此任何節點X 到根節點的路徑 一定是唯一的, 這個路徑 就是TRIE裡所存儲的字符串;
@DELI;
一般TRIE树 就是2个操作: {插入(一个字符串), 查询(一个字符串)}; 如果有需要 你可以添加(删除) TRIE是支持的; 一般不会涉及到(修改)操作;
@DELI;
假如你對TRIE的需求是: 詢問一個字符串是否是TRIE中的某個字符串的前綴, 並不在乎出現的次數;
那麼此時 由於動態開點的性質 其實你不需要記錄額外信息(比如每個節點記錄一個exist 表示該節點/字符串是否存在) 不需要的, 你可以直接去遍歷 假如訪問到了空節點(即未開闢的節點) 那麼說明 當前字符串不是TRIE中的一個前綴;
但是有些信息 是動態開點所無法知道把的, 比如把需求改為(是否是TRIE中的某個字符串), 即把的前綴去掉, 那麼此時就出錯了; 假如TRIE裡有個字符串abcd, 你此時查詢ab 那麼他其實是前綴 而不是字符串;
那麼你可能認為 假如一個節點 他的兒子都是-1(未開闢) 那麼就說明他是字符串 而不是前綴, 這也是錯誤的, 比如TRIE裡 你放了"ab", "abcd", 那麼對於ab 他既是abcd的前綴 也是ab字符串;
因此 最好還是記錄信息;
@DELI;
雖然是動態開點 但TRIE本質上 他就是一個簡單的K叉樹, 千萬不要受動態開點的影響 不要只看已經開闢的點, 他就對應 一個K叉樹 有些點是亮的 其他點都是暗的(表示還未使用), 但是本質上 他就是一個K叉樹;
@DELI;
一個長度為N的字符串"abc", 他對應(用到了)TRIE樹中的N+1個點 對應["", "a", "ab", "abc"]這些前綴, 即 你往TRIE裡放一個字符串 實際上 是放了N個前綴(忽略"");
因此 TRIE樹本質 就是處理有關前綴的問題;
@MARK: @LOC_0;
@LINK: https://www.acwing.com/problem/content/description/4193/;
根據異或的前綴和性質, 對於A[l]^...^A[r] 他等於 sum[r] ^ (A[1]^...^A[l-1]), 因此 把sum[1,2,...,r-1]放到TRIE裡 可以求一個區間最大異或和;
注意 這兩個區間[l1, r1] [l2,r2] 其中並不一定有r1 + 1 = l2, 因此 你只枚舉一個點i 找他往前和往後的片段 是錯誤的;
正確做法是: 先對數組正向處理一遍 得到V[i] = (...^A[i-1]^A[i])的最大值), 然後令Ma[i] = Max( V[1,2,....,i]); 然後再在數組反向的處理一遍 配合Ma[] 更新答案;
@DELI;
@LINK: https://www.acwing.com/problem/content/description/4194/;
兩個字符串a,b可以匹配
⟺
\iff
⟺ a是b的前綴 或 b是a的前綴;
對於一個字符串集合S, 給定一個字符串x 求S中有多少字符串可以和x匹配;
#算法#: 將S存儲到TRIE樹中, 每個節點x(設其對應的字符串為T)記錄: End[x]: S中T的個數; Prefix[x]: S中(不等於自身的)前綴為T的字符串個數, 對於要查詢的字符串x 比如為abcd, 則答案為Prefix[ abcd] + End[ a | ab | abc];
@DELI;
https://editor.csdn.net/md/?articleId=129461499
. 对整数的异或操作, 进行DFS, 求最优解;
@DELI;
namespace __TrieTree{
using __String_ = ?; // Trie樹所存儲的數據類型, 他的長度 就對應Trie樹的高度;
static constexpr int __BranchesCount_ = ?; // 每個點的分支個數
static constexpr int __NodesMaximum_ = ?; // 總節點個數
struct __Node_{
public:
int Son[ __BranchesCount_];
void Initialize(){
memset( Son, -1, sizeof( Son));
}
friend ostream& operator<<( ostream & _cout, const __Node_ & _a){
_cout<< "[";
FOR_( i, 0, __BranchesCount_-1){
if( i > 0){ _cout<<",";}
_cout<< _a.Son[i];
}
_cout<< "]";
return _cout;
}
};
int __NodesCount; // 動態開點 當前已經使用了`[0,NodesCount-1]`這些點;
__Node_ __Nodes[ __NodesMaximum_]; // `Nodes[a].Son[b]=c`: `a`號節點的 第`b`個分支兒子的編號為`c` (如果`c=-1` 說明這個兒子節點還尚未存在);
void Initialize(){
__NodesCount = 1; // 根節點的編號為`0`;
for( int i = 0; i < __NodesMaximum_; ++i){
__Nodes[ i].Initialize();
}
}
void Insert( const __String_ & _str){
int curId = 0;
for( cur : _str){
int branchId = @TODO;
ASSERT_WEAK_( 0 <= branchId && branchId < __BranchesCount_);
if( __Nodes[ curId].Son[ branchId] == -1){
ASSERT_WEAK_( __NodesCount < __NodesMaximum_);
__Nodes[ curId].Son[ branchId] = __NodesCount ++;
}
curId = __Nodes[ curId].Son[ branchId];
//>< `_str`的`[...cur]`這個前綴 對應在Trie樹中的節點編號為`curId`;
}
//>< `_str` 對應在Trie樹中的節點編號為`curId`; (注意不要和上一行重複了 上一行也會得到`_str`這個字符串);
}
? Query( const __String_ & _str){
?t ANS = 0;
int curId = 0;
for( cur : _str){
int branchId = @TODO;
ASSERT_WEAK_( 0 <= branchId && branchId < __BranchesCount_);
if( __Nodes[ curId].Son[ branchId] == -1){ // `_str`的`[...cur]`這個前綴 並不存在於樹中;
return @TODO;
}
curId = __Nodes[ curId].Son[ branchId];
//>< `_str`的`[...cur]`這個前綴 對應在Trie樹中的節點編號為`curId`;
}
//>< `_str` 對應在Trie樹中的節點編號為`curId`; (注意不要和上一行重複了 上一行也會得到`_str`這個字符串);
return ANS;
}
void __Debug(){
DE_( "*Trie-Debug*: begin");
function dfs = [&]( int _curId, string _str){
bool isLeaf = true;
for( int branchId = 0; branchId < __BranchesCount_; ++branchId){
if( __Nodes[ _curId].Son[ branchId] != -1){
isLeaf = false;
dfs( __Nodes[ _curId].Son[ branchId], _str + char('0' + branchId));
}
}
if( isLeaf){
DE_( _str);
}
};
dfs( 0, "");
DE_( "*Trie-Debug*: end");
}
} // namespace __TrieTree
虽然他称为字典树, 但我认为 叫做(前缀树)更好;
比如, 有N个字符串S, M次询问, 对于每次循环 给定一个字符串o, 问S中有多少个字符串s 满足o是s的前缀
设所有字符串长度均为L, 则如果暴力, 时间是: (M * N * L)
如果使用Trie, 可以做到: (N * L) + (M * L)
对于一个串(或数字 一个数字也是个串嘛), 先将其转换为一个: P进制的串
(之所以说’串’, 而不是P进制数, 是因为: 在这里, 前导零是起作用的), 或者说, 这里不涉及其十进制数值大小问题, 所以称之为 P进制串;
… 即, 假如原串长度是N, 则其对应的(P进制串) 长度也必须是N
即, 所有串, 都是个(P进制串), 即所有字符 都是[0, P)之间的数字
Trie为一个(P叉树), 即每个节点 都有P个儿子, 他的结构 还是很简单的, 就是个(P叉树)
R
A0 |A1 |A2 ... |A(p-1)
B00 B01 ... B0(p-1) |B10 B11 ... B1(p-1) | ...
C...
A0, B0 都代表 P进制中 0这个数字; A1, B1代表1这个数字;
一个节点x, 他代表: 从根R 到 x节点的路径, 所有(除了)R的节点, 所代表的P进制串
比如, B10这个节点, 代表(A1, B10), 即(1 0)这个P进制串
比如, 一个字符串(abc), 他对应的P进制串为(0 1 2)
那么, C012这个节点, 就代表这个串; 因为C012他代表的路径是: (R, A0, B01, C012)
节点个数
但是, 如果我们真的构造出这个P叉树来, 存储空间肯定是不够用的;
这个P叉树, 每一层的节点个数是:
(
P
0
,
P
1
,
P
2
,
P
3
,
.
.
.
)
(P^0, P^1, P^2, P^3, ...)
(P0,P1,P2,P3,...)
假如字符串长度是1e5, P = 26, 那么: 整个树 至少有
2
6
1
e
5
26^{1e5}
261e5个节点, 这爆空间了;
而假如最多有10个字符串, 即最多只会涉及到 (1e6)个节点, 根本不需要完整构造出整个树来
节点ID
以一个3叉树为例:
1
2 |3 |4
5 6 7 |8 9 10 |11 12 13
对于当前节点x, 他的儿子, 一定是(3 * x - 1, 3 * x, 3 * x + 1)
也就是, 所有的节点ID, 都规定死了
那么, 和上面的问题一样, 如果以这样方式, 到了第1e5层, 节点ID早就爆LL了, 也就无法表示节点ID了
由于上面多种原因, 因此, Trie使用的是: 动态开点
@DELI;
#动态开点#
每个节点, 依然有P个儿子, 这点不变;
比如当前点x 代表的串是(a b c); 那么, 他的儿子 一定代表一个长度为4的串 (a b c ?)
但是整个树, 一开始 并不创建出来, 而是在每次 (往Trie中, 插入字符串)时, 构造树
… 即这个插入的字符串, 用到多少个节点, 再临时开辟节点
令根节点的ID为: Root = 0, 全局记录一个Trie_id = 1;(表示当前已经开辟了Trie_id个节点)
int Trie[ N][ P]; 这就是Trie的核心, N为你最多使用多少个节点, P为P叉树
… 对于b = Trie[ a][ i], 表示: ID为a的节点(他有P个儿子), 他的第i个儿子, 其ID为b
… 比如, ID为a的节点 代表串为(0 1 2), 那么b = Trie[ a][ 3], 则ID为b的节点 代表串(0 1 2 3)
也就是, Trie里存的是: 儿子的ID号;
一开始, Trie是空的, 所以, memset( Trie, -1), 表示所有节点 还没有开辟 (除了Root)
比如要插入(a b c)这个字符串, 其对应的P进制串为(0 1 2)
变量cur = 0 (表示当前所在的节点ID), 此时的cur 表示的是个(空串)
依次遍历P进制串
1, 数字为0, 则判断Trie[ cur][ 0]这个节点 是否有开辟(即是否等于-1)
… 如果没有开辟, 则令Trie[ cur][ 0] = Trie_id ++;
更新: cur = Trie[ cur][ 0]; 此时的cur, 就代表(0)这个串
2, 数字为1, 同样如果Trie[ cur][ 1]这个节点没有开辟 则开辟
更新: cur = Trie[ cur][ 1]; 此时的cur, 就代表(0 1)这个串
3, 数字为2, 同样如果Trie[ cur][ 2]这个节点没有开辟 则开辟
更新: cur = Trie[ cur][ 2]; 此时的cur, 就代表(0 1 2)这个串
@DELI;
#背景#: 有2個操作{插入(字符串),查詢(字符串)} (這是一個標準TRIE樹的應用場景), 但是需要同時維護(版本信息) 就像一個Git系統一樣, 可以回退版本 也可以在某個版本的基礎上再進行插入操作;
. 顯然要實現一個(節點為一個TRIE樹)的Git系統, 你用暴力的方式 (每個節點 就是一個單獨的TRIE) 但這會超時, 而因為 TRIE樹的插入操作(插入一個長度為N的字符串) 他只會使用到(N+1)個節點, 即當前TRIE為A 往裡面插入一個字符串後 得到TRIE為B 那麼 B只有N+1個節點 是與A不同的, 而B的其他所有節點的信息 和A的 是完全一樣的, 因此借用指針/引用的概念 我們可以讓B裡面的這些(與A相同的)節點 就指向A的節點 (兩者完全相同), 因此 AB這兩個TRIE 有如下性質: (本質結構相同 這點非常重要 不管動態開點這個性質 他倆都是(每個點有Branches個分支)) 基於這個性質 比如說對於某個字符串C 他對應在A裡的節點為a 對應在B裡的節點為b, 那麼此時有2種情況: 要麼a=b(這說明你的插入操作 不會訪問到這個節點 換句話說C不是你插入的字符串的前綴, 此時a/b的值 可能是nullptr即沒有開闢節點 也可能!=nullptr 雖然開闢了節點 但兩者的節點是同一個內存), 要麼a!=b 這說明 你B裡新插入的字符串 會訪問到這個節點(即C是你插入的字符串的前綴) 那麼此時a,b兩者的內存一定不同(雖然他倆都代表C這個字符串 這就是前面講的本質結構是相同的);
#算法#: 每個節點 一定有一個int Son[ Branches]; 他記錄 (當前節點的兒子的下標) 就相當於是指針(指向了他的兒子 -1表示兒子還沒有開闢), 這種存儲方式的好處在於 你只要得到根節點root 就等價於 你得到了整個TRIE樹 (順藤摸瓜); 比如 此時的TRIE為A 他的根節點為RA 其版本號為VA, 我要在他的基礎上 進行插入操作(插入字符串012) 然後得到一個新版本VB, 首先 申請一個新節點RB(因為你插入的字符串 一定會訪問根節點 只要是會訪問到的節點 就要原版本的節點 不同) 執行Node[RB] = Node[RA] (由於一個根節點 就代表了一整個TRIE樹, 因此你這個操作 意味著 此時RB就代表了A這個TRIE!), 因為要插入012這個字符串 然後你要移動到son = Node[ RB].Son[ 0] 此時有2種情況: {1(son!=-1):[這說明 你要訪問的這個節點 在A裡是存在的(此時不同共用 你只要會訪問的節點 就必須和A的不同), 你需要開闢一個新節點new 然後讓Node[ new] = Node[son] 這個操作非常重要 這意味著(以new為根的樹 此時就是以son為根的樹) 最後讓Node[ RB].Son[0] = new 更改當前節點的這個兒子], 2(son=-1):[此時就開闢一個新節點new 然後讓Node[ RB].Son[0] = new即可 因為son在A裡而沒有子樹的 因此不需要向1:一樣 做拷貝子樹的操作}; 然後繼續遍歷整個字符串 操作都是一樣的;
#區間版本的查詢#
一般的查詢 即回退到某個版本R, 然後在R這個TRIE上進行查詢 這很簡單;
假設TRIE的修改操作只有插入, 假如說兩個版本L,R 且(L是R的祖先版本 即在L的基礎上 新添加了若干個字符串S後得到了R版本), 你需要求 新添加的這些字符串S的信息, 有點類似於前綴和思想, 我們舉個實際的例子:
字符串序列S[N], 對S[l...r]這個區間的字符串 進行查詢(可以認為是 把這些S[l...r]字符串 放到一個TRIE裡 進行查詢操作), 做法是: 令第i版本的TRIE為S[...i] 即此時你有N個TRIE版本, 然後每個節點 存儲count 表示(以當前字符串為前綴的元素個數, 即你插入一個字符串"abc"時 會執行"a".count++, "ab".count++, "abc".count++), 那麼此時 假如你要查詢一個字符串"xyz" 在S[l+1, ..., r]這些字符串裡 進行查詢, 令"x"在L版本的TRIE裡的節點為LID 在R版本的TRIE裡為RID (這裡一定要聯繫的TRIE的(不同版本的TRIE樹的本質結構是相同的)這一性質) @IF(LID是不存在的):[你只比較RID即可 即如果RID.count>0 說明"x"是S[l+1 ...r]裡的某個字符串的前綴 那麼可以繼續往下遍歷] @ELSE(LID存在):[令c = RID.count - LID.count 這表示的 S[l+1 ...r]裡面 有多少個字符串 他的前綴是等於"x"的, 如果c>0 說明滿足條件 則可以繼續往下遍歷]; 這個count屬性 本身也是有前綴和的性質的, 即對於"abcd" 你會令"a".count += 1, 也就是 比如"a".count = 2 那麼說明有2個字符串 他的前綴是"a", 再根據 此時只有插入操作(沒有修改/刪除) 因此對於任何字符串 他在R版本的count值 一定是>= 其在L版本的count值的, 因此 這兩個值 是可以進行相減的 (這裡的邏輯要搞清楚) 你讓"xxx"在R版本的count - "xxx"在L版本的count 這個值 就等於: S[l+1, ...,r]這些字符串裡 有多少個 他的前綴是等於"xxx";
一個序列A, 第i個版本的TRIE樹 存儲A[0...i]這些數, 對於區間查詢A[l...r] 就對應為 第r版本的TRIE樹RT 減去 第l-1版本的TRIE樹LT, 這裡的減去 是指的RT與LT一一對應的節點信息的相減, 即我們構造一個TRIE樹T 他的節點x的信息 等於RT的x節點信息減去LT的x節點信息, 那麼會有T等於存儲A[l...r]這些數的TRIE樹; 當然你要保證 這個節點信息 是符合相減性質的;
@DELI;
template< class _TypeItem_, int _BranchesCount_>
class ___TrieTree_Persistent{
//<
// 一個TRIE樹(即某個版本的TRIE樹) 他對應與一個(字符串的集合), 換句話說 一個TRIE樹 和 一個字符串集合 是等價的;
// `_TypeItem_`: Trie樹所存儲的元素的數據類型, 比如`TypeItem=string` 那麼他的每個*字符*就對應Trie上的*節點*, 一個字符串的最大長度 決定了Trie樹的高度;
// `_BranchesCount_`: 每個點的分支個數;
public:
class __Node_{
public:
int SonId[ _BranchesCount_]; // `b=SonId[a]`: @IF(`b==-1`):[當前節點的第`a`個兒子暫未開闢], @ELES:[兒子為`Nodes[b]`];
int Count; // 對於某個TRIE樹(他對應的字符串集合為`S`), 對於任意字符串C 令其對應在TRIE的節點為`x` 則`x.Count`表示:[`S`中 前綴為`C`的字符串的個數];
//< 比如Trie裡只有一個"abc", 那麼`["a"/"ab"/"abc"].Count==1`;
__Node_(){ Initialize();}
void Initialize(){
memset( SonId, -1, sizeof( SonId)); Count = 0;
}
friend ostream& operator<<( ostream & _cout, const __Node_ & _a){
__Debug_list( _a.SonId, _a.Count, "\n");
return _cout;
}
};
vector<__Node_> Nodes; // `Nodes[a].SonId[b]=c`: `a`號節點的 第`b`個分支兒子的編號為`c` (如果`c=-1` 說明這個兒子節點還尚未存在);
//< 動態開點 當前已經使用了`[0,...,Nodes.size()-1]`這些節點;
vector VersionRoot; // `VersionRoot[a]=b`: `a`號版本的Trie樹的根節點為`Nodes[b]`;
//< 當前已經有`[0,...,VersionRoot.size()-1]`這些版本;
vector VersionFa; // `VersionFa[a]=b`: `a`號版本的父節點為`b`, 如果`b==-1` 說明`a`版本在Git樹中為*根節點*;
//< `VersionFa.size()=VerionRoot.size()`
void Initialize( int _nodesEstimateMaximum_, int _versionsEstimateMaximum){
//< `nodesEstimateMaximum`:[預估的總節點個數]; `versionsEstimateMaximum:[預估的總版本個數];
Nodes.reserve( _nodesEstimateMaximum_); Nodes.clear();
VersionRoot.reserve( _versionsEstimateMaximum); VersionRoot.clear();
VersionFa.reserve( _versionsEstimateMaximum); VersionFa.clear();
}
void Insert( pair _flag, const _TypeItem_ & _str){
//< @IF(`flag.first=1`):[以`flag.second`號版本為父節點 創建一個新的版本(版本號為`VersionRoot.size()`)];
// @ELIF(`flag.first==-1`):[直接修改`flag.second`號版本 但要確保*這個版本一定是Git上的葉子節點* 即沒有`VersionFa[?]=flag.second`];
// @ELIF(`flag.first==0`):[直接創建一個*沒有父節點*的新版本(版本號為`VersionRoot.size()`)];
int curId; // 當前所操作Trie樹的根節點;
if( _flag.first == 1){ // 在父版本的基礎上 創建新版本
ASSERT_( IsInInterval_( _flag.second, 0, (int)VersionRoot.size()-1, true));
curId = Nodes.size();
Nodes.push_back( Nodes[ VersionRoot[ _flag.second]]); // 複製
VersionRoot.push_back( curId);
VersionFa.push_back( _flag.second);
}
else if( _flag.first == 0){ // 創建(無父節點的)新版本
curId = Nodes.size();
Nodes.emplace_back(); // 完全*空的*樹;
VersionRoot.push_back( curId);
VersionFa.push_back( -1);
}
else if( _flag.first == -1){ // 在已有版本上進行操作
ASSERT_( IsInInterval_( _flag.second, 0, (int)VersionRoot.size()-1, true));
ASSERT_MSG_( "確保不存在`VersionFa[?]==flag.second`, 即該版本是Git上的*葉子節點*;");
curId = VersionRoot[ _flag.second];
}
for( auto cur : _str){
int branchId = @TODO(`cur`對應的分支ID);
ASSERT_WEAK_( ::Tools::IsInInterval_( branchId, 0, _BranchesCount_-1, true));
if( Nodes[ curId].SonId[ branchId] == -1){ // 當前要訪問的節點不存在
Nodes[ curId].SonId[ branchId] = Nodes.size(); Nodes.emplace_back();
}
else{ // 當前要訪問的節點已經存在
if( _flag.first == 1){ // 父節點已經有當前這個節點了, 需要新拷貝一個節點
Nodes.push_back( Nodes[ Nodes[ curId].SonId[ branchId]]);
Nodes[ curId].SonId[ branchId] = (int)Nodes.size() - 1;
}
}
curId = Nodes[ curId].SonId[ branchId];
//>< `_str`的`[...cur]`這個前綴 對應在Trie樹中的節點編號為`curId`;
Nodes[ curId].Count ++;
}
//>< `_str` 對應在Trie樹中的節點編號為`curId`;
}
int Query( int _lv, int _rv, const _TypeItem_ & _str){
//< 令`T`為一個`TypeItem`的集合, 則當前函數是在`T`這個集合裡 對`_str`進行查詢, `T`的定義如下:
// @IF(`lv=-1`):[`rv`這個版本的Trie裡所有的`TypeItem`組成的集合 即為`T`];
// @ELSE(`lv!=-1`):[確保`lv`在Git樹中一定是`rv`的*祖節點*, 令`lv`版本的TRIE樹所對應的字符串集合為`SL` 令`rv`版本對應的字符串集合為`SR`, 則`T`等於差集`SR/SL`];
// . 注意 這裡的`lv,rv` 和前綴和思想很像 但有一點不同, 這裡是不包含`lv`的 即實際上你查詢的是`[lv+1, ..., rv]`這個區間 (即這些`(lv,rv]`版本所調用的修改操作);
ASSERT_( _lv>=-1 && _lv<=_rv && _rv>=0 && _rv<(int)VersionRoot.size());
int rightId = VersionRoot[ _rv];
int leftId;
if( _lv == -1){
leftId = -1;
}
else{
ASSERT_MSG_( "確保`lv`在Git樹中一定是`rv`的*祖節點*");
leftId = VersionRoot[ _lv];
}
for( auto cur : _str){
int branchId = @TODO(`cur`對應的分支ID);
ASSERT_WEAK_( ::Tools::IsInInterval_( branchId, 0, _BranchesCount_-1, true));
int count; // `T`裡面 前綴為`str[...cur]`的字符串的個數
if( Nodes[ rightId].SonId[ branchId] == -1){
count = 0;
}
else{
count = Nodes[ Nodes[rightId].SonId[branchId]].Count;
if( leftId != -1 && Nodes[ leftId].SonId[ branchId] != -1){
count -= Nodes[ Nodes[leftId].SonId[branchId]].Count;
}
}
if( count > 0){
}
else{
//>< `T`集合是空的;
return;
}
ASSERT_( Nodes[ rightId].SonId[ branchId] != -1);
if( leftId != -1){ leftId = Nodes[ leftId].SonId[ branchId];}
rightId = Nodes[ rightId].SonId[ branchId];
//>< `_str`的`[...cur]`這個前綴 對應在Trie樹中的節點編號為`curId`;
}
//>< `_str` 對應在Trie樹中的節點編號為`curId`;
}
friend ostream& operator<<( ostream & _cout, const ___TrieTree_Persistent & _tr){
__Debug_list( "\n", "*Trie-Debug-Begin*", "\n");
__Debug_list( _tr.VersionRoot, _tr.VersionFa, "\n");
FOR_( v, 0, (int)_tr.VersionRoot.size()-1){
function dfs = [&]( int _curId, string _str){
bool isLeaf = true;
for( int branchId = 0; branchId < _BranchesCount_; ++branchId){
if( _tr.Nodes[ _curId].SonId[ branchId] != -1){
isLeaf = false;
dfs( _tr.Nodes[ _curId].SonId[ branchId], _str + char('0' + branchId));
}
}
if( isLeaf){
__Debug_list( _str, "\n");
}
};
__Debug_list( "Version(" + to_string(v) + ")-Begin", "\n");
dfs( _tr.VersionRoot[ v], "");
__Debug_list( "Version(" + to_string(v) + ")-End", "\n");
}
__Debug_list( "*Trie-Debug-End*", "\n");
return _cout;
}
}; // class ___TrieTree_Persistent
___TrieTree_Persistent< int, 2> Tr;
Tr.Initialize( N*30, M);
FOR_( i, 0, N-1){
if( i == 0){ Tr.Insert( {0,1}, ?);}
else{ Tr.Insert( {1,i-1}, ?);}
}
之前講過 對於只有(插入)操作的TRIE, 要判斷一個字符串/前綴 是否存在, 你可以直接通過Son[]兒子的指針 來判斷其是否開闢 也就意味著 他是否存在;
但是在(區間版本的查詢)這裡, 你要涉及到2個版本之間的相減 因此就需要用到count這個額外信息來維護 (表示某個前綴出現的次數), 對於某字符串S 用Version[R].count - Version[L].count 這個值 就代表了 從(L版本之後開始 到R版本結束) 這個階段 所新加的字符串集合裡面 前綴為S的字符串的個數;
@LINK: https://editor.csdn.net/md/?not_checkout=1&articleId=133611997;