Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
欢迎关注我的个人博客：www.zuzhiang.cn
以前只知道字典树可以降低空间复杂度，今天无意中接触了 01字典树，原来可以用它来降低时间复杂度，下面我就来给大家介绍一下 01字典树的原理和应用。
01字典树主要用于解决求异或最值的问题。我先放上简单的模板，然后再讲解它的原理。
int tol; //节点个数
LL val[32*MAXN]; //点的值
int ch[32*MAXN][2]; //边的值
void init()
{ //初始化
tol=1;
ch[0][0]=ch[0][1]=0;
}
void insert(LL x)
{ //往 01字典树中插入 x
int u=0;
for(int i=32;i>=0;i--)
{
int v=(x>>i)&1;
if(!ch[u][v])
{ //如果节点未被访问过
ch[tol][0]=ch[tol][1]=0; //将当前节点的边值初始化
val[tol]=0; //节点值为0，表示到此不是一个数
ch[u][v]=tol++; //边指向的节点编号
}
u=ch[u][v]; //下一节点
}
val[u]=x; //节点值为 x，即到此是一个数
}
LL query(LL x)
{ //查询所有数中和 x异或结果最大的数
int u=0;
for(int i=32;i>=0;i--)
{
int v=(x>>i)&1;
//利用贪心策略，优先寻找和当前位不同的数
if(ch[u][v^1]) u=ch[u][v^1];
else u=ch[u][v];
}
return val[u]; //返回结果
}01字典树和普通的字典树原理类似，只不过把插入字符改成了插入二进制串的每一位（0或1）。
通过上面的代码，我们可以发现有下面几个事实：
1. 01字典树是一棵最多 32层的二叉树，其每个节点的两条边分别表示二进制的某一位的值为 0 还是为 1. 将某个路径上边的值连起来就得到一个二进制串。
2.节点个数为 1 的层（最高层）节点的边对应着二进制串的最高位。
3.以上代码中，ch[i] 表示一个节点，ch[i][0] 和 ch[i][1] 表示节点的两条边指向的节点，val[i] 表示节点的值。
4.每个节点主要有 4个属性：节点值、节点编号、两条边指向的下一节点的编号。
5.节点值 val为 0时表示到当前节点为止不能形成一个数，否则 val[i]=数值。
6.可通过贪心的策略来寻找与 x异或结果最大的数，即优先找和 x二进制的未处理的最高位值不同的边对应的点，这样保证结果最大。
例题：
一、HDU 4825
传送门：HDU 4825
题目大意：在一组数中找跟某个数异或结果最大的数。
题解：直接套用模板，将数组中的数插入到 01字典树，对每一个数查询即可。
二、HDU 5536
传送门：HDU 5536
题目大意：在一个数组中找出 (s[i]+s[j])^s[k] 最大的值，其中 i、j、k 各不相同。
题解：HDU 5536 题解
三、BZOJ 4260
传送门：BZOJ 4260
题目大意：给你 n 个数，让你求两个不相交的区间元素异或后的和的最大值。
题解：BZOJ 4260 题解
四、POJ 3764
传送门：POJ 3764
题目大意：在树上找一段路径（连续）使得边权相异或的结果最大。
题解：POJ 3764 题解
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/196363.html原文链接：https://javaforall.net
