Trie树学习总结
字典树，又称前缀树，是用于快速处理字符串的问题，能做到快速查找到一些字符串上的信息。
另外，Trie树在实现高效的同时，会损耗更多的空间，所以Trie是一种以空间换时间的算法。
Trie的思想
Trie的思想十分简单，其实我在很早之前就已经懂了Trie的思想，只不过一直没有实现，所以就……
咕咕，没事，Trie无论是思想还是代码思想都还是很简单。现在我重新再搞回Trie也很快就代码实现了。
Trie是思想其实用图更容易展现。下面放一张图给大家看看，相信大家很快就会明白了。
如果我们插入字符串：
zlh
AK
tql
AKIOI
AKnoip
上面就是一颗我们建的Trie树。
如果我们要查找“zlh”，那么就会沿着1->2->3点找下去。
如果我们要查找“AKIOI”，那么我们就会沿着4->5->9->10->11点找
也可以十分容易发现"AK"是"AKIOI"的前缀。
那么大家现在应该就能明白Trie的构造了吧。
简单说就是顺着之前Trie树的构造去插入点，例如我们最后插入"AKnoip"，就会先走过"A"和"K"，然后发现没有匹配的字符了，就先后新建了'n','o','i','p'，这几个点。复杂度O(len(字符串))。
查询就会沿着Trie的构造一个一个跳，所以查询复杂度是O(len(字符串))。
那么Trie的思想就是这样了。
Trie的实现
明白了思想，实现就应该很简单了吧，这里通过一道例题来实现Trie。
题目：P2580 于是他错误的点名开始了
定义
struct kkk{int son[27],cnt;bool flag;
}trie[maxn];首先是插入操作：
void insert(string s){int len=s.size(),u=0; //获取长度len，u是当前点的编号，根的编号是0for(int i=0;i<len;i++){int v=s[i]-'a'; //获取位置if(!trie[u].son[v]) //如果没有继续下去的节点trie[u].son[v]=++num; //就新建一个u=trie[u].son[v]; //跳到下一个点去插入}trie[u].flag=true; //标记此处是一个单词
}然后是查询操作：
int find(string s){int len=s.size(),u=0;for(int i=0;i<len;i++){int v=s[i]-'a'; //同上if(!trie[u].son[v])return 3; //找不到返回没有u=trie[u].son[v]; //同上}if(trie[u].flag==false)return 3; //不是一个单词就返回没有if(!trie[u].cnt){ //如果没有被点过trie[u].cnt++; //标记被点过了return 1; //返回有} return 2; //不然返回重复
}那么Trie的实现就这样了。
Trie的考点
- 异或XOR以及利用XOR的性质
- 后缀转前缀
- 记忆化，缩点，重构树，Trie的思想（见 P3294 [SCOI2016]背单词，P2292 [HNOI2004]L语言
- 可持久化（详见下文
随便给点题
phone list
The XOR Largest Pair
Nikitosh 和异或
Immediate Decodability
[SCOI2016]背单词
[HNOI2004]L语言
[USACO08DEC]秘密消息Secret Message
最长异或路径
做完上面那几道应该就能了解Trie了
习题讲解
1、phone list
题目：Phone list
题目意思十分明确，求有没有一个字符串是其他字符串的前缀，如果有就返回"NO"，没有返回"YES"。
这题和前面讲的Trie的作用一模一样，可以快速判断一个字符串是不是已插入的字符串中的前缀。
那么这道题就很简单了，我们先将全部字符串都插入到Trie中。
然后查找每一个字符串，如果字符串下有儿子，那么就代表当前字符串是某个字符串的前缀，直接返回。
代码实现也很简单，可以算是Trie的模板题。
#include<bits/stdc++.h>
using namespace std;
struct kkk{int son[11],sum;bool flag;void clear(){memset(son,0,sizeof(son));sum=0;flag=0;} //清0
}trie[400001];
int n,T,num;
string S[400001];
void insert(string s){int len=s.size(),u=0;for(int i=0;i<len;i++){int v=s[i]-'0';if(!trie[u].son[v])trie[u].son[v]=++num;trie[u].sum++; //表示u有多少个儿子u=trie[u].son[v];}trie[u].flag=true;
}
int find(string s){int len=s.size(),u=0;for(int i=0;i<len;i++){int v=s[i]-'0';if(!trie[u].son[v])return 0; //找不到字符串就返回u=trie[u].son[v];}if(trie[u].sum==0)return 0; //如果没有儿子就代表不是前缀return 1; //否则就是前缀
}
int main(){scanf("%d",&T);while(T--){num=0; //记得清0for(int i=0;i<=400000;i++)trie[i].clear(); //记得清0scanf("%d",&n);for(int i=1;i<=n;i++){cin>>S[i];insert(S[i]); //一个一个插入}bool ans=false;for(int i=1;i<=n;i++){int res=find(S[i]); //查询if(res==1){ans=true;break;} //判断是不是前缀}if(ans==true)printf("NO\n"); //输出else printf("YES\n");}
}2、Immediate Decodability
题目：Immediate Decodability
这道题和上面那道题一模一样，不过输入比较恶心，而且数据范围也比较小。
这里的输入就是不断输入字符串S，然后将字符串S插入到Trie中，直到S='9'为止。
到了S='9'，就将之前的S都像上面的一样查询一边，输出答案，然后清0。
代码：
#include<bits/stdc++.h>
using namespace std;
struct kkk{int son[11],sum;bool flag;void clear(){memset(son,0,sizeof(son));sum=0;flag=0;}
}trie[2001];
int n,T,num,t;
string S[400001];
void insert(string s){int len=s.size(),u=0;for(int i=0;i<len;i++){int v=s[i]-'0';if(!trie[u].son[v])trie[u].son[v]=++num;trie[u].sum++;u=trie[u].son[v];}trie[u].flag=true;
}
int find(string s){int len=s.size(),u=0;for(int i=0;i<len;i++){int v=s[i]-'0';if(!trie[u].son[v])return 0;u=trie[u].son[v];}if(trie[u].sum==0)return 0;return 1;
}
void solve(){ //解决之前的字符串bool ans=false;for(int i=1;i<=n;i++){int res=find(S[i]);if(res==1){ans=true;break;}}if(ans==true)printf("Set %d is not immediately decodable\n",t);else printf("Set %d is immediately decodable\n",t);
}
int main(){n=1;while(cin>>S[n]){if(S[n]=="9"){t++;solve(); //解决之前的问题memset(trie,0,sizeof(trie)); //清0num=0;n=1;continue; //清0}insert(S[n]);n++; //如果不是‘9’就插入}
}3、The XOR Largest Pair
题目：The XOR Largest Pair
这道题是一道变向的Trie，也是Trie的一个基本应用。
思路：
1、首先将a[i]转换为二进制的字符串存起来，记得空位要补0
2、然后将这些字符串都插入到Trie里。
3、查询每一个字符串，找到以每一个数和另外其他数的最大异或和。
那么问题就是怎么找一个数和另外其他数的最大异或和了。
我们知道，异或是不同就为1，相同就为0，所以我们因尽量让高位的二进制为1。
所以我们查询的时候就倒着查，也就是如果s[i]为0，那么我们就查1。但是没有1怎么办，我们总不能就此放弃吧，于是我们继续查0。
最后取个最大值就OK了。
看看代码：
#include<bits/stdc++.h>
using namespace std;
struct kkk{int son[3],sum;bool flag;void clear(){memset(son,0,sizeof(son));sum=0;flag=0;}
}trie[4000001];
int n,T,num,ans;
int x[1000001];
void insert(string s){ //插入int len=s.size(),u=0;for(int i=0;i<len;i++){int v=s[i]-'0';if(!trie[u].son[v])trie[u].son[v]=++num;trie[u].sum++;u=trie[u].son[v];}trie[u].flag=true;
}
int find(string s){int len=s.size(),u=0,ans=0,num=(int)(2147483648ll/2ll);for(int i=0;i<len;i++){int v=((s[i]-'0')^1); //倒着查if(!trie[u].son[v])v^=1; //找不到就倒回来else ans+=num; //不然就累加进去u=trie[u].son[v];num/=2; //跳下一个}return ans;
}
string decompose(int x){ //拆分成二进制string s="";while(x!=0)s+=(x%2)+'0',x>>=1;while(s.size()!=31)s+='0';reverse(s.begin(),s.end());return s; //返回字符串
}
int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&x[i]);string s=decompose(x[i]);insert(s);}for(int i=1;i<=n;i++){int res=find(decompose(x[i]));ans=max(ans,res); //取最大值}printf("%d\n",ans);
}4、[USACO08DEC]秘密消息Secret Message
题目大意：给你n个信息和m个密码，要你求出对于每一个密码都多少信息，使这些信息的前缀和密码的前缀相同。
理解清题目，这道题就很简单了，我们用信息来在建立Trie时多维护一个数据sum，存的是有多少个信息经过这个节点。那么我们在查询时，先统计有多少信息是密码的前缀再加上当前节点的sum就是答案。
#include<bits/stdc++.h>
using namespace std;
struct kkk{int son[11],sum,flag;void clear(){memset(son,0,sizeof(son));sum=0;flag=0;}
}trie[400001];
int n,T,num,ans;
string S[400001];
void insert(string s){int len=s.size(),u=0;for(int i=0;i<len;i++){int v=s[i]-'0';if(!trie[u].son[v])trie[u].son[v]=++num;u=trie[u].son[v];trie[u].sum++; //记录sum}trie[u].flag++; //有重复所以要加加
}
int find(string s){int len=s.size(),u=0,ans=0;for(int i=0;i<len;i++){int v=s[i]-'0';if(!trie[u].son[v])return ans; //找不到u=trie[u].son[v];ans+=trie[u].flag; //记录信息是密码前缀}return ans-trie[u].flag+trie[u].sum; //-trie[u].flag是为了去重
}
int main(){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){int x;scanf("%d",&x);string s="";char c;for(int j=1;j<=x;j++)cin>>c,s+=c;insert(s);}for(int i=1;i<=m;i++){int x;scanf("%d",&x);string s="";char c;for(int j=1;j<=x;j++)cin>>c,s+=c;ans=find(s);printf("%d\n",ans);}
}5、Nikitosh 和异或
题目在这里：「一本通 2.3 例 3」Nikitosh 和异或
首先对于如何求异或最大值我们已经在上文学到了，现在我们要求的是两个没有覆盖的区间异或的和。
异或有一个性质：就是据有可减性，也就是说我们记前缀异或sum数组，如果求[l,r]的异或和，那么答案就是sum[r]^sum[l-1];后缀异或也是一样的
所以我们可以对于每一个位置i都求一遍以i为结尾的区间中，最大的区间异或值。方法是将i前面的每一个前缀sum数组都插入到Trie中，然后find(sum[i])，答案计为l数组。
另外，对于每一个位置i都求一遍以i为开头的区间中，最大的区间异或值。方法是将i后面的每一个后缀sum数组都插入到Trie中，然后find(sum[i])，答案计为r数组。
那么对于每一个位置i，都统计前面的最大的l，记录下来。表示的是i前面的最大区间异或和
对于每一个位置i，都统计后面的最大的r，记录下来。表示的是i后面的最大区间异或和
那么答案就是对于每一个位置i的 前面的最大区间异或和 和 后面的最大区间异或和 的 和 的最大值
代码：
#include<bits/stdc++.h>
using namespace std;
struct kkk{int son[3];void clear(){memset(son,0,sizeof(son));}
}trie[8000001];
int n,T,num,ans;
int x[1000001],l[1000001],r[1000001],s[35];
void insert(int x){int j=-1,u=0;memset(s,0,sizeof(s));while(x){s[++j]=x&1;x>>=1;}for(int i=31;i>=0;i--){if(!trie[u].son[s[i]])trie[u].son[s[i]]=++num;u=trie[u].son[s[i]];}
}
int find(int x){int ans=0,u=0;for(int i=31;i>=0;i--){int v=1-s[i];if(!trie[u].son[v])v^=1;else ans+=(1<<i);u=trie[u].son[v];}return ans;
}
int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&x[i]);}int sumx=0;num=0;for(int i=1;i<=n;i++)sumx^=x[i],insert(sumx),l[i]=max(l[i-1],find(sumx));memset(trie,0,num+1);sumx=0;num=0;for(int i=n;i>=1;i--)sumx^=x[i],insert(sumx),r[i]=max(r[i+1],find(sumx));for(int i=1;i<n;i++)ans=max(ans,l[i]+r[i+1]);printf("%d\n",ans);
}