【算法笔记】Trie树
前言
我的数学老师说过：你学精通一个东西比学很多东西有用的多。
于是就有了这个。
Trie树
Trie（字典树），又被叫做 踹树
它珂以实现快速的字符串搜索。
我们在搜索引擎里面输入词汇的时候，搜索引擎可能会给你跳出它猜测你可能要搜索的内容，这里就是运用了Trie树的。
（所以它还是挺实用的）
它的结构原理其实有一点点像单词接龙。
比如：
luogu 和 luogugubird
字典树就会将其储存成 luogugubird （在我们开的线性表角度看）
也就是说，它会把单词的重叠前缀叠加储存。
基本结构
我们首先要知道的是，Trie 的每一个节点都有很多个字符指针，它们分别对应着一些字符。
这是字典树的一张图：
（当然单词应该是小写的，我的画板出了一些问题，见谅）
Trie 树开始时只有一个根节点（蓝色节点）。
而每一个节点都有几个字符指针，它们储存（对应）着一些字符
(c,a,t,e,p)
而我为什么把最后的节点都标红了呢？
这就涉及到了 Trie 的思想了。
简单来说，Trie的结构是这样的：
对于英文字符串，其每个节点包括26个字符指针.
每个指针对应一个字母，即每一条边为一个字母.
同时每个节点包括一个标识，表示从根节点到该节点的边是否组成了一个单词。
而我们查找一个单词的关键，就是这个红色的标记（代表着一个单词的结尾）。
它可以帮助我们判断我们检索到的字符串是不是一个单词。
同时也是插入和检索的终止的一个标志。
两个操作：插入与查找
插入（Insert）
假设现在我们有一个字符串 \(s\)
那么先让一个指针（指向节点） \(P\) 指向 \(root\) 。
然后再依次扫描 \(s\) 的每一个字符 \(c\) , 过程如下：
-
如果 \(P\) 的 \(c\) 字符指针指向了一个已经存在的节点 \(q\) ，让 \(P =q\) （有存储过这个字符，让它与相同的字符的重合）
-
如果 \(P\) 的 \(c\) 字符指针没有指向任何一个节点，新建一个节点，让 \(P\) 的 \(c\) 字符指针指向这个节点，然后让 \(P =\) 这个节点。（没有就新加入一个）
（说再多还不如一个动画）：
Code：
void insert(char* str){
int len=strlen(str);
int p=1;
for(register int k=0;k检索(search)
如果我们需要检索一个单词是否存在于Trie 之中，很明显需要那个end[]标记的帮助，他可以帮助我们快速判定当前字符串的情况。
那么，和Insert一样 ，我们令一个指针（指向节点） \(P\) 指向 \(root\) ,然后向下检索 \(s\) 的每一个字符 \(c\)。
会出现以下的两种情况：
-
当前的 \(P\) 的 \(c\) 字符指针 指向了一个空的节点（没有指向节点）。证明这个字符串 \(s\) 的剩下的字符都没有按顺序插入过 \(Trie\) ，结束。
-
当前的 \(P\) 的 \(c\) 字符指针 指向了一个节点 \(q\) ，则令 \(P=q\) ，继续搜索。
如果我们搜索完 \(s\) 的时候，刚好节点 \(P\) 是被打过标记的(color=red) ，证明 \(s\) 存在于这个Trie 之中，返回真。
图的话可以看一看上面那一个（做这个gif很麻烦的啊），唯二的区别就是在没找到的时候 \(Insert\) 是加入 而 \(Search\) 是返回。在搜完的时候 \(Insert\) 是打上标记， \(Search\) 是确认标记.
Code:
bool search(char* str){
int len=strlen(str);
int p=1;
for(register int k=0;k还有一点一定要记住， Trie 在开始的时候一定要记得初始化！
Code：
void init(){
memset(trie[0],0,sizeof(trie[0]));
memset(end,0,sizeof(end));
tot=1;
}
另外，说一下，Trie不是只能维护26个英文字符。你可以自己改进（比如后三道题就是维护异或和的（01Trie））
Trie例题：
-
P1481 魔族密码
-
P2580 于是他错误的点名开始了
-
UVA11362 Phone List （下面那一道的重题）
-
SP4033 PHONELST - Phone List
01Trie
基本结构
01Trie是一种主要用于维护异或问题的数据结构。
你也可以把它看做是只有 0 1 的Trie
（也就是把数字转成2进制存进 Trie 里面）。
它在插入的时候和正常 Trie 不太一样。
他是把数字 按位 插入进 Trie 里面的。
也就是把数字从最高位依次插入进 Trie 里面。
所以我们需要用到一点点位运算技巧：
int cacid(int num,int pos){
return (num>>pos)&1;
}
也就是,对于一个数 \(num\) ， \(\operatorname{cacid}(num,pos)\) 返回 \(num\) 第 \(pos\) 位的bit值。
插入
一般情况下，我们处理的都是 32位整数(int) ,所以01Trie一般最多有 32 层。
那么，我们用 \(\operatorname{cacid}()\) 函数，还有一点点二进制思想。
可以改出来一个这样子的代码：
int cacid(int num,int pos){
return (num>>pos)&1;
}
void insert(int num){
int p=0;
for(register int i=32;i>=0;--i){
int ch=cacid(num,i);
if(!trie[p][ch]){//如果节点未被访问过
trie[tot][0]=trie[tot][1]=0;//将当前节点的指针初始化
value[tot]=0;//节点值为0，表示到此不是一个数
trie[p][ch]=++tot;
}
p=trie[p][ch];
}
value[p]=num;//节点值为 num，即到此是一个数
}
检索
我们每次在查询的时候，最基础的操作都是查询和 \(num\) \(\operatorname{xor}\) 之后的结果最大的数是多少。
怎么做呢？
和检索search()肯定是类似的。
不过我们要根据 \(\operatorname{xor}\) 的性质来检索。
还是去取一个指针 \(P\) ，扫描\(num\) 的每一位 \(bit\) 值:
-
每一次都去访问和当前位 \(ch\) 相反的那一个指针.
-
如果没有（相反位指针指向空），那就只能访问 \(P\) 对应的的 \(ch\) 指针。
根据异或的性质，我们就可以找到和 $num $ 异或之后是最大值的那个数。
举个例子(这里为了方便，简化成了\(3\)位)：
那么询问 \(011\) 时，就是这样的：
代码实现：
long long query(long long num){
int p=0;
for(register int i=32;i>=0;--i){
int ch=cacid(num,i);
if(trie[p][ch^1]){
p=trie[p][ch^1];
}
else{
p=trie[p][ch];
}
}
return value[p];
}
你会发现，我只是把 end[] 搞成了 value[]。
策略改了一改。
因为01Trie 和 Trie 并没有太大的不同。
那么，来几道题练一下手：
01Trie例题：
-
Loj10050 （可能是P6018的基础）
-
Loj10056 (可能是P6018的基础)
-
（选做）P6018 [Ynoi2010]Fusion tree
可持久化Trie
没开工（没学完）