01树

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
转移自老blog

01树

/*******01字典树部分********/
int ch[maxn*100][2];int tot=0;int root[maxn];
//新建N个字典树

//向根为u的字典树插入x
void insert(int u,int x){
    for(int i=18;i>=0;i--){
        int id=(x>>i)&1;
        if(!ch[u][id])
            ch[u][id]=++tot;
        u=ch[u][id];
    }
}
//查询根为u的字典树与x的异或最大值
int query(int u,int x){
    int res=0;
    for(int i=18;i>=0;i--){
        int id=(x>>i)&1;
        if(ch[u][id^1]){
            u=ch[u][id^1];
            res|=(1<<i);
        }
        else u=ch[u][id];
    }
    return res;
}
/*****01字典树部分结束**********/