字典树是一种树形结构，典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较
图示如下
例题： Acwing.143最大异或对
在给定的 N 个整数 A1，A2……AN 中选出两个进行 xor（异或）运算，得到的结果最大是多少？
输入格式
第一行输入一个整数 N。
第二行输入 N 个整数 A1～AN。
输出格式
输出一个整数表示答案。
数据范围
1≤N≤105,
0≤Ai<231
输入样例：
3
1 2 3
输出样例：
3
#include<bits/stdc++.h> using namespace std; int tire[101000*31][2],a[101000]; int id; void insert(int x) { int p=0; //根节点 for(int i=30;i>=0;i--) //从最大位开始找 { int u=x>>i&1; //取x的第i位二进制数是什么 if(!tire[p][u]) //如果插入中发现没有该子节点，开出这条路 tire[p][u]=++id; p=tire[p][u]; //指针指向下一层 } } int find(int x) { int p=0,sum=0; //用sum来存取当前路径表示的数是什么 for(int i=30;i>=0;i--)//从最大位开始找 { int u=x>>i&1; if(tire[p][!u]) //如果当前层有对应的不相同的数 p=tire[p][!u],sum=sum*2+1;//p指针就指到不同位置的地址，*2代表左移1位 加上下一位 else { p=tire[p][u]; sum=sum*2; } } return sum; } int main() { int n,sum=0; cin>>n; id=0; for(int i=0;i<n;i++) { cin>>a[i]; insert(a[i]); } for(int i=0;i<n;i++) { sum=max(sum,find(a[i])); } cout<<sum<<endl; }
