01 Trie

Cindy_Li · 2023-08-21 16:55:24 · 个人记录

01 Trie

字符集为 \{0,1\} 的字典树 Trie

一般用于解决异或相关问题

基本问题

给定数集 S 和数 x，求 \max\{x \oplus S_i\}。

从高到低将集合 S 中的数插入 Trie（注意高位要补齐）。

从根节点开始，尽量选和 x 当前位不同的，计算答案。

容易证明这一定是最大值。

时空复杂度 O(|S|\log S_i)

int tot=0;
int son[N*35][2];
inline void build(LL x){
    int pos=0;
    for(int i=33;i>=0;i--){
        int bit=(x>>i)&1;
        if(!son[pos][bit]) son[pos][bit]=++tot;
        pos=son[pos][bit];
    }
}
inline LL query(LL x){
    int pos=0;LL ans=0;
    for(int i=33;i>=0;i--){
        int bit=(x>>i)&1;
        if(son[pos][bit^1]) 
            pos=son[pos][bit^1],ans+=(1ll<<i);
        else pos=son[pos][bit];
    }
    return ans;
}

变式 0

给定数集 S 和数 x，求 \min\{x \oplus S_i\}。

很简单，每次尽量选和 x 当前位相同的就好。

变式 1-1

给定数集 S，求两两最大异或和。

对每个数都做一次基本问题就好了。

因为自己异或自己是 0，不影响答案，所以预处理 01Trie，查询取最大值就结束了。

复杂度还是 O(|S|\log S_i)

变式 1-2

给定序列 A ，求 max_{1\le l\le r\le n}\{A_l \oplus \dots \oplus A_r\}。

根据异或的性质，可以推出

那么就转化成对于 A 的前缀和 S 做变式 1-1。

注意！S_0 也要加入 Trie！

扩展 1

给定数集 S 和数 x，求第 k 大异或和。

类似权值线段树求区间第 k 小的思路。

对 Trie 上每个点，记录子树大小（出现次数），让 k 跟和 x 不同的子树比大小，小就走和 x 不同；大就走和 x 相同，k 减去不同的子树大小。

int tot=0;
int son[N*35][2],siz[N*35];
inline void build(LL x){
    int pos=0;
    for(int i=33;i>=0;i--){
        int bit=(x>>i)&1;siz[pos]++;
        if(!son[pos][bit]) son[pos][bit]=++tot;
        pos=son[pos][bit];
    }
    siz[pos]++;
}
inline LL query(LL x,LL rk){
    int pos=0;LL ans=0;
    for(int i=33;i>=0;i--){
        int bit=(x>>i)&1;
        if(!son[pos][bit^1]) pos=son[pos][bit];
        else if(rk<=siz[son[pos][bit^1]]) 
            pos=son[pos][bit^1],ans|=1ll<<i;
        else rk-=siz[son[pos][bit^1]],pos=son[pos][bit];
    }
    return ans;
}

扩展 1-1

给定数集 S，求两两第 k 大异或和。

优先队列维护对每个数来说，异或和第 t 大（初始 t 为 1）

每次取出堆顶，将第 t+1 大加入队列。

可以保证第 i 次取到的数是第 i 大。

由于每个异或和会统计两次（两数交换），所以第 2k 次取到的就是答案。

扩展 2

给定一棵带权树，求树上最大异或路径。

（某些人可能就想写树剖了，但你别急

记 dis(i,j) 代表从点 i 到 j 的路径异或和。

由于根节点到 lca(i,j) 的路径是重复的，所以 dis(i,j)=dis(rt,i)\oplus dis(rt,j)。

问题转化成给定数集求两两最大异或和。

01 Trie 是个挺神奇的东西qwq

如果有错误或者不清楚的地方欢迎评论/私信