（发文的目的是为了记录学习算法的历程，而不是教程）
引子
如果想要再字典里查找“salieri”这个单词，我们会怎么做，比较朴素（bushi）的想法是从字典的第一个单词翻到最后一个单词，这种方法虽然（蠢）简单，但是却很花时间，当然，
聪明（正常）的你肯定会按照索引来查找，而字典树正是借用了这种索引的思想。
字典树Trie
来看下面这张图:
从根节点出发（根节点不存储字符），按某条路径走最后可以得到一个单词比如 1->2->5就得到了aa。字典树的结构相当的简单。
下面代码是封装成结构体的字典树
点击查看代码
#include<bits/stdc++.h>
using namespace std;
struct Trie {
int trie[10000][26],cnt=0; //cnt记录当前节点的个数。其次根据记录在树中的字符不同，26这个范围可能会变
bool exist[10000]; //exist 数组记录当前节点是否为某个单词的结尾
void insert(string& s);
bool find(string& s);
};
//插入一个单词
void Trie::insert(string& s) {
int p = 0;
for (int i = 0; i < s.size(); i++) {
int c = s[i] - 'a';
if (!trie[p][c]) trie[p][c] = ++cnt;
p = trie[p][c];
}
exist[p] = trie;
}
//寻找某个单词是否存在
bool Trie::find(string& s) {
int p = 0;
for (int i = 0; i < s.size(); i++) {
int c = s[i] - 'a';
if (!trie[p][c]) return false;
p = trie[p][c];
}
return exist[p];
}
01Trie
如果将二进制数看成01字符串，我们也可以将其存入字典树中，我们将二进制数从高位开始存入字典树中，
从而我们可以快速的求出某两个数最大或最小的异或和
例题：
【模板】字典树
Macesuted 给了你 n 个整数。
他想要知道任意两数异或和最大是多少。
参考代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int trie[10000005][2], cnt;
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n; cin >> n;
vector<int>a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
int p = 0;
for (int j = 30; j >= 0; j--) { //二进制数最多有31位，从最高位开始存入
int c = (a[i] >> j) & 1; //通过位运算求出某一位
if (!trie[p][c]) trie[p][c] = ++cnt;
p = trie[p][c];
}
}
int ans = 0;
for (int& x : a) { //遍历每一个数，求与其它数的最大异或和
int tans = 0, p = 0;
for (int i = 30; i >= 0; i--) {
int c = (x >> i) & 1; //如果当前位是0，有1就走1，否则走0；反之同理。
if (trie[p][1 - c]) {
tans = tans | 1;
tans = tans << 1;
p = trie[p][1 - c];
}
else if (trie[p][c]) {
tans = tans << 1;
p = trie[p][c];
}
else break;
}
ans = max(tans, ans);
}
cout << (ans >> 1) << endl;