01 Trie：最大异或对

算法理解

异或值的大小优先由高位决定。因此查询某个数 x 时，从第 30 位向下走：当前位是 0 就优先找 1，当前位是 1 就优先找 0。这样能尽可能让结果的高位为 1。

• 适用：非负整数的最大异或对。
• 复杂度：每次插入、查询都是 O(31)；总计 O(31n)。
• 注意：数组大小要按 数字个数 × 位数 预留；处理 long long 时应从第 62 位开始。

模板代码

// 01Trie 最大异或对
const int N=100005;
int tree[N*32][2],cnt=1;
void insert(int a)
{
	int k=0;
	for (int i=30;i>=0;i--)
	{
		int c=(a>>i)&1;
		if (!tree[k][c]) tree[k][c]=cnt++;
		k=tree[k][c];
	}
}
int find(int x)
{
	int k=0,ans=0;
	for (int i=30;i>=0;i--)
	{
		int y=(x>>i)&1;
		if (tree[k][!y]) ans|=(1<<i),k=tree[k][!y];
		else k=tree[k][y];
	}
	return ans;
}