初学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];
}