引入

众所周知，Trie 是维护一堆字符串的数据结构，那么如果我们把数看做二进制字符串，用 Trie 维护，会得到什么呢？

答案是 01-Trie。

01-Trie 利用贪心思想，能够方便地维护异或最大、最小、第 $k$ 大以及相关信息。

基础操作

在大多数 01-Trie 中，我们按照数的二进制位从高到低建立。

插入

同普通 Trie。

1
2
3
4
5
6
7
8
9
10
11
12
struct node{
    int e[2];
}t[N*T];
int tot=0;
void ins(int x){
    int p=0;
    for(int i=T;i>=0;i--){
        int c=(x>>i)&1;
        if(!t[p].e[c])t[p].e[c]=++tot;
        p=t[p].e[c];
    }
}

异或最大

下面实现一种最常用的操作：查询在这些数中异或值 $x$ 最大的异或值。

我们知道异或时，当两位不相同时为 $1$，否则为 $0$。

现在就有了一个基本思路：尽量在 Trie 上沿着数的相反位走。

那么为什么这是对的呢？考虑如果从小到大第 $k$ 为本来能往反方向走，却走了相同的方向，那么后面 $k-1$ 位就算全部往反方向走，也最多只有 $\sum_{i=1}^{k-1}2^i=2^k-1$ 的贡献，但是如果我们在第 $k$ 位往反方向走，那么就有 $2^k$ 的贡献，显然比前者大。

1
2
3
4
5
6
7
8
9
int query(int x){
    int p=0,ans=0;
    for(int i=T;i>=0;i--){
        int c=(x>>i)&1;
        if(t[p].e[c^1])p=t[p].e[c^1],ans+=(1ll<<i);
        else p=t[p].e[c];
    }
    return ans;
}

异或第 $k$ 大

好的现在你已经完全理解了。

给定值 $x$，求其异或 Trie 里的数出来的第 $k$ 大结果。

为了实现这一操作，我们对插入操作稍作修改，记录子树里有多少个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
struct node{
    int e[2],v;
}t[N*T];
int tot=0;
void ins(int x){
    int p=0;
    for(int i=T;i>=0;i--){
        int c=(x>>i)&1;
        if(!t[p].e[c])t[p].e[c]=++tot;
        p=t[p].e[c];
        t[p].v++;
    }
}

假设我们到了一个节点 $p$，且当前 $x$ 的下一二进制位是 $b$，现在我们要选择 $p$ 往哪个方向走。

如果 $p$ 往下只有一个儿子，那么只能走这一个儿子，无可置疑。

看看 $p$ 与 $b$ 相反的儿子里有多少个数，如果这个数量小于 $k$，那么答案一定不在这个节点里面，直接往 $b$ 走。

否则，让 $k$ 减去这个数量，往 $b$ 相反的儿子走。

1
2
3
4
5
6
7
8
9
int kth(int x,int k){
	int p=0,ans=0;
	for(int i=T;i>=0;i--){
		int c=(x>>i)&1;
		if(!t[p].e[c^1]||t[t[p].e[c^1]].v<k)k-=t[t[p].e[c^1]].v,p=t[p].e[c];
		else p=t[p].e[c^1],ans+=(1ll<<i);
	}
	return ans;
}