世界的尽头

Trie 树

Trie 树也叫字典树，是一种按照“前缀”组织数据的树形结构。普通 Trie 常用于存储字符串：从根节点开始，每条边代表一个字符，从根到某个节点的路径就表示一个字符串前缀。

当数据是非负整数时，也可以把每个整数写成固定长度的二进制串，再存入 Trie。此时：

每个节点最多有两个子节点，分别表示下一位是 0 或 1；
从高位到低位插入，根到叶子的路径表示一个完整整数；
具有相同高位前缀的整数会共用一段路径。

这种结构称为二进制 Trie，常用于最大异或、最小异或等按位贪心问题。

数组模拟二进制 Trie

在 ACM 模式中，节点总数上限已知时，可以使用二维数组保存每个节点的两个子节点：

const int N = 100010;
 
int son[31 * N][2];
int idx;

其中：

son[p][0] 表示节点 p 的 0 子节点编号；
son[p][1] 表示节点 p 的 1 子节点编号；
0 号节点既是根节点，又利用全局数组初始值为 0 的性质表示“子节点不存在”；
idx 表示已经创建的最后一个节点编号，新节点编号为 ++idx。

如果最多插入 $n$ 个不超过 $10^9$ 的非负整数，每个整数需要处理二进制第 $30$ 位到第 $0$ 位，共 $31$ 位，因此最多创建约 $31n$ 个节点。

插入一个整数

插入整数 x 时，从最高位开始依次取出每个二进制位。如果对应的子节点不存在，就创建一个新节点；随后移动到该子节点。

void insert(int x) {
  int p = 0;
 
  for (int i = 30; i >= 0; i--) {
    int bit = (x >> i) & 1;
 
    if (son[p][bit] == 0) {
      son[p][bit] = ++idx;
    }
 
    p = son[p][bit];
  }
}

表达式

(x >> i) & 1

先把 x 的第 i 位移动到最低位，再通过按位与取出这一位。

查询与 `x` 异或最大的数

异或运算的规则是：

`a`	`b`	`a ^ b`
0	0	0
0	1	1
1	0	1
1	1	0

两个二进制位不同时，异或结果为 1。为了让最终异或值尽可能大，查询时应该从最高位开始：

设 x 当前位为 bit；
优先寻找值为 bit ^ 1 的子节点，使当前异或位为 1；
如果相反位不存在，只能选择与 bit 相同的子节点，当前异或位为 0。

int query(int x) {
  int p = 0;
  int result = 0;
 
  for (int i = 30; i >= 0; i--) {
    int bit = (x >> i) & 1;
    int opposite = bit ^ 1;
 
    if (son[p][opposite] != 0) {
      result |= 1 << i;
      p = son[p][opposite];
    } else {
      p = son[p][bit];
    }
  }
 
  return result;
}

当找到相反位时，异或结果的第 i 位为 1，可以通过

result |= 1 << i;

把这一位设置为 1。如果只能选择相同位，该位异或结果就是 0，不需要修改 result。

为什么优先选择高位相反一定最优

二进制数的高位比所有更低位之和还大。对于第 i 位：

2^i > 2^{i-1} + 2^{i-2} + \cdots + 2^0.

因此，只要能让当前第 i 位的异或结果为 1，即使后面所有低位都为 0，也一定优于当前位为 0、后面低位全部为 1 的方案。

所以，从高位到低位，每一步优先选择相反位的局部最优决策，可以保证最终异或值全局最大。

AcWing 143：最大异或对

题意

给定 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$ ，从中选择两个数，使它们的异或值最大，输出这个最大值。

即求：

\max_{1 \le i,j \le n}(a_i \oplus a_j).

思路

朴素做法枚举所有数对，需要 $O(n^2)$ 的时间，无法通过 $n=10^5$ 的数据范围。

可以先把所有整数插入二进制 Trie。对于每个整数 a[i]，再沿 Trie 查询与它异或最大的整数。所有查询结果的最大值就是答案。

查询过程不必恢复 Trie 中具体选择了哪个数，只需要直接累加每一位能够得到的异或值。

完整代码

#include <algorithm>
#include <iostream>
 
using namespace std;
 
const int N = 100010;
 
int n;
int a[N];
int son[31 * N][2];
int idx;
 
void insert(int x) {
  int p = 0;
 
  for (int i = 30; i >= 0; i--) {
    int bit = (x >> i) & 1;
 
    if (son[p][bit] == 0) {
      son[p][bit] = ++idx;
    }
 
    p = son[p][bit];
  }
}
 
int query(int x) {
  int p = 0;
  int result = 0;
 
  for (int i = 30; i >= 0; i--) {
    int bit = (x >> i) & 1;
    int opposite = bit ^ 1;
 
    // 优先选择与当前位不同的分支，使这一位的异或结果为 1
    if (son[p][opposite] != 0) {
      result |= 1 << i;
      p = son[p][opposite];
    } else {
      p = son[p][bit];
    }
  }
 
  return result;
}
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
 
  cin >> n;
 
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    insert(a[i]);
  }
 
  int answer = 0;
 
  for (int i = 0; i < n; i++) {
    answer = max(answer, query(a[i]));
  }
 
  cout << answer << '\n';
 
  return 0;
}

样例

输入：

3
1 2 3

输出：

解释：

1 ^ 2 = 3
1 ^ 3 = 2
2 ^ 3 = 1

因此最大异或值为 3。

正确性说明

对任意一个整数 x，query(x) 从最高位到最低位确定 Trie 中匹配整数的每一位。

在第 i 位，如果相反位分支存在，选择它会使异或结果的第 i 位为 1；任何选择相同位的方案在这一位都只能得到 0。由于第 i 位的权值大于所有更低位权值之和，因此选择相反位一定更优。

如果相反位分支不存在，则 Trie 中所有具有当前前缀的候选数在这一位都与 x 相同，只能选择相同位分支。按照这一规则逐位选择后，query(x) 得到的就是 x 与数组中某个数异或的最大值。

主程序对每个 a[i] 都执行一次查询，因此所有可能成为最优数对第一个元素的情况都会被考虑，最终取最大值就得到整个数组的最大异或对。

复杂度分析

每个整数固定处理 $31$ 个二进制位：

建树时间复杂度： $O(31n)=O(n)$ ；
查询时间复杂度： $O(31n)=O(n)$ ；
总时间复杂度： $O(n)$ ；
空间复杂度： $O(31n)=O(n)$ 。

这里的 $31$ 是固定常数。

常见错误

从低位向高位贪心

异或值首先由最高的不同位决定。如果从低位开始选择，低位的局部最优可能会阻止高位得到 1，无法保证答案最大。必须从最高位向最低位遍历。

节点数组空间不足

每插入一个整数，最坏可能新建 $31$ 个节点，因此数组大小应至少为：

int son[31 * N][2];

只开 son[N][2] 会发生数组越界。

混淆节点编号 `0` 的两种作用

代码让 0 号节点作为根节点，同时让 son[p][bit] == 0 表示子节点不存在。新节点必须从 1 开始编号，所以创建节点时使用 ++idx，不能使用 idx++ 后直接赋值。

忘记给移位表达式加括号

建议明确写成：

int bit = (x >> i) & 1;

这样可以直观看出先右移、再取最低位，避免阅读和修改代码时混淆运算顺序。

位数与数据范围不匹配

本题整数不超过 $10^9$ ，处理第 $30$ 位到第 $0$ 位即可。如果题目使用更大的整数，应改用 long long，并根据数据范围增加 Trie 的层数，同时使用 1LL << i 进行移位。

7-Trie 树