字典树（Trie）是一个比较简单的数据结构，也叫前缀树，用来存储和查询字符串。
具体是以怎样的存储方式呢，如图：
我们可以发现，正如其别名前缀树一样，具有相同前缀的字符串共享同一个树枝干，直到不同的地方才会分开来
具体对这个字典树的讲解，我们便分析板子边考虑：
#include<bits/stdc++.h>
#define maxn 100010
using namespace std;
int son[maxn][26],idx,cnt[maxn];
void insert(string str){
int p = 0;
for(int i = 0 ;i<str.size(); i++){
int u = str[i] - 'a';
if(!son[p][u]) son[p][u] = ++idx;
p = son[p][u];
}
cnt[p]++;
}
int query(string str){
int p = 0;
for(int i = 0;i<str.size();i++){
int u = str[i] - 'a';
if(!son[p][u]) return 0;
else p = son[p][u];
}
return cnt[p];
}
int main(){
std::ios::sync_with_stdio(false); std::cin.tie(0);
int n;
cin>>n;
while(n--){
char order;
cin>>order;
string str;
cin>>str;
if(order == 'I') insert(str);
else cout<<query(str)<<'\n';
}
return 0;
}
解释：我们在这里idx表示的是第几个结点，然而我们不是如同平常一样每读入一个字符串才令idx++，而是对字符串的每一个字符都当作一个结点，然后有些字符串是共享一部分的结点的；然后我们会发现在insert函数中，我们在彻底读入这个字符串之后，会令cnt[p]++，p表示的是当前这个叶子结点位置，说明这个字符串数量增一。 然后我们解释一下son，son的第一维表现的是第几个节点，第二维指的是该结点之后可能走到的所有位置，如果走到了，那么存储的值就是++idx，不然就是0；
关于单链表，双链表，trie，堆的idx的辨析可以看一下：AcWing 835. 如何理解单(双)链表，Trie树和堆中的idx？ - AcWing
然后除了这里的普通的字典树，有一个比较有趣的就是01字典树，它存储的就可以是数字，而且是以二进制位的方式读入的，方便贪心的去解决求解按位异或，按位或求最值这种问题；
#include<bits/stdc++.h>
#define maxn 5000100
using namespace std;
int son[maxn][2],idx;
int a[maxn];
int find(int x){
int p = 0 ;
int i = 31 ;
int ans = 0;
for(;i>=0;i--){
int u = 0;
if(x & (1<<i)) u = 1;
if(u == 1 && son[p][0]) {ans+=(1<<i);p = son[p][0];}
else if(u == 0 && son[p][1]) {ans+=(1<<i);p = son[p][1];}
else if(u == 1 && son[p][1]) p = son[p][1];
else if(u == 0 && son[p][0]) p = son[p][0];
else return ans;
}
return ans;
}
void insert(int x){
int i = 31;
int p = 0;
for(;i>=0;i--){
int u = 0;
if(x & (1<<i)) u = 1;
if(!son[p][u]) son[p][u] = ++idx;
p = son[p][u];
}
}
int main()
{
std::ios::sync_with_stdio(false); std::cin.tie(0);
int n;
cin>>n;
for(int i = 1;i<=n;i++){
cin>>a[i];
insert(a[i]);
} //把当前值先分别保存在数组中和字典树中
//然后就是遍历树，直接去找到对应的那个最大值
int maxi = -1;
for(int i = 1; i<=n; i++){
maxi = max(maxi , find(a[i]));
}
cout<<maxi;
return 0;
}
分析：这里有几个比较细节的问题需要分析哈，我们先暂且不管；我们总的来分析一下为了找到这个异或最大值，是怎么做的，我们还是创建一颗字典树，但是我们是以二进制的方式进行存储（用按位与和逻辑左移就可以哈），然后每一位去比较，如果当前是1就去找有没有对应位是0的，反之去找1（这里就体现了一个贪心的思路，因为就算后面全得到1也不及当前的这个1大，所以只需要求局部最优解就可以），并且ans要及时加上这个对应位的值（1<<i）如果没有就遍历下一位。
然后比较细的地方就在于：因为是按位与，所以我们在insert的时候，即使前面全是0，我们也要放入到字典树中，这样是方便在遍历时每一位都对应；
假设我们有 1e5 个数，极限情况下，31 位都不一样，所以我们需要 31× 1×10^5+1的空间（根节点也算），所以我们开 4×10^6 的空间就行了
总结：
字典树是一种空间换时间的数据结构，我们牺牲了字符串个数×字符串平均字符数×字符集大小的空间，但可以用 的时间查询，其中
为查询的前缀或字符串的长度。