初学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];
}
全部评论

相关推荐

VirtualBool:都去逗他了?
点赞 评论 收藏
分享
04-16 19:19
已编辑
合肥大学 Java
刷了100道题的大老虎很想提桶:27届现在早没日常hc了,不可能找到的,等暑假9月吧
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务