初学01字典树(持续摸索中)
01字典树听名字便知是用字典树来维护一个01串即一个二进制数的数据结构。字典树又称前缀树,他和hash在查询映射这方面各有优劣。
现在介绍的01字典树在处理区间异或这方面上往往非常常用,现在我们来一一展开。
对于一个十进制的数字而言,我们可以将它的二进制从前往后的每一位都取下来,然后模仿字典树的方式进行插入,最终会形成一个只含01的一棵树,形似二叉树,因为每一个结点最多只有俩个左右子结点。
现在我们拿一道例题出来进行分析
hdu 4825:题意,给出n个数和m次查询,每次查询给一个数字s,问在n个数中哪个数字与s的异或值最大。
首先是初始化与插入
int ch[32*maxn][2],val[32*maxn]; int sz=0;//节点数 void init() { sz=0; memset(ch,0,sizeof ch); memset(val,0,sizeof val); } void insert(int x) { int root=0; per(i,31,0) { int b=(x>>i) & 1;//取出第31-i位 if(!ch[root][b]){ ch[root][b]=++sz; } root=ch[root][b]; } val[root]=x;//最终结点代表这个放的数字 }
理解一下插入过程,这很重要。
接下来是查询,我们使用贪心策略,要使异或出来的值最大,那么最优肯定是异或出来的每一位都是1,那么就要求在n个数中选出一个与s所有位数尽可能不一样的那个数,因此我们贪心地从前往后搜寻,要是有位数不一样的就选它,要是没有就被迫选择一样的。
代码如下:
int query(int x) { int root=0; per(i,31,0) { int b=(x>>i) & 1; if(ch[root][b ^ 1])//贪心策略,优先选与当前位置不一样的,即b^1 { root=ch[root][b ^ 1]; } else root=ch[root][b];//被迫只能选择相同的 } return val[root]; }