01树


转移自老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字典树部分结束**********/

文章作者: fightinggg
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 fightinggg !
  目录