如何用 0-1 字典树（二进制 Trie）求数组中的最大异或对？

简化版

把每个数字按二进制位（从最高位到最低位）插入一棵只有 0/1 两个分支的 Trie（0-1 Trie）。求某个数能得到的最大异或值时，贪心地在每一位都尽量走”相反”的分支（当前位是 0 就找 1、是 1 就找 0，因为相异的位异或得 1，让高位尽量为 1 结果最大）。这样把「两两异或求最大」从 O(n²) 降到 O(n × 位数)。

详细版

问题：给一个数组，求任意两个数异或的最大值 max(a[i] ^ a[j])。

暴力：两两异或，O(n²)。

0-1 Trie 解法：

// 把每个数按 31~0 位插入（int 用 32 位，或按数据范围取位数）
void insert(int x) {
    Node node = root;
    for (int i = 31; i >= 0; i--) {
        int b = (x >> i) & 1;              // 取第 i 位
        if (node.child[b] == null) node.child[b] = new Node();
        node = node.child[b];
    }
}
// 求 x 与树中已有数的最大异或
int maxXor(int x) {
    Node node = root; int res = 0;
    for (int i = 31; i >= 0; i--) {
        int b = (x >> i) & 1;
        if (node.child[b ^ 1] != null) {   // 优先走相反位（异或得 1）
            res |= (1 << i);               // 这一位能取到 1
            node = node.child[b ^ 1];
        } else {
            node = node.child[b];          // 只能走相同位（这一位异或是 0）
        }
    }
    return res;
}

流程：边遍历数组边把数插入 Trie，对每个数用 maxXor 求它和已插入的数的最大异或，取全局最大。O(n × 32)。

完整版教学

一、为什么按位建 Trie

异或是按位运算：两个数异或，每一位独立，相同为 0、相异为 1。要让异或结果最大，就要让尽量高的位为 1。这自然引导我们按二进制位、从高位到低位来处理——而 Trie 正好能把「按位逐层决策」表示成一棵树：每个节点两个分支（0 和 1），从根到叶的路径就是一个数的二进制表示。

二、贪心：每一位尽量走相反的分支

求 x 与树中某数的最大异或，从最高位开始贪心：

异或某一位得 1，需要两个数这一位不同。
所以在 Trie 里，x 的当前位是 b，我们优先走 b^1（相反）的分支——如果这个分支存在，说明树里有数在这一位和 x 不同，异或这一位能得 1，且因为是从高位开始，这个「1」的价值最大。
如果相反分支不存在，只能走相同分支（这一位异或是 0），继续看下一位。

贪心为什么正确：高位的 1 比低位所有位加起来还大（2^k > 2^k−1 + … + 1）。所以只要能让高位取 1，就一定比「高位取 0、低位全取 1」更优。逐位贪心走相反分支，得到的就是全局最大异或。

三、走一个直觉例子

树里有 2(010)、5(101)，求 3(011) 的最大异或：
从高位到低位处理 3 = 0 1 1
- 最高位 0：找相反 1 → 5 那条路存在，走它，这一位异或=1
- 中间位 1：沿 5(101) 走，5 这位是 0，与 3 的 1 相反 → 异或=1
- 最低位 1：5 这位是 1，与 3 相同，只能走，异或=0
结果 3^5 = 6 (110)  ✓（比 3^2=1 大）

四、复杂度

插入：每个数按位插入，O(位数) = O(32)。
查询最大异或：每个数逐位贪心，O(32)。
总体 O(n × 32) = O(n)（位数是常数），远优于暴力的 O(n²)。
空间 O(n × 32) 存 Trie 节点。

五、延伸应用

0-1 Trie 是一类「异或 / 位运算最值」问题的通用工具：

数组中最大异或对（本题）。
区间最大异或、异或和满足条件的对数（配合前缀异或和）。
可持久化 0-1 Trie：处理带历史版本的异或查询。
一些「最大/最小异或路径」的图论题也会用到。

核心套路都是「按位建 Trie + 逐位贪心」。

六、常见误区与追问

考点	正确口径
建树	按二进制位从高到低插入每个数
贪心	查询时每位优先走相反 bit
答案	逐位累加可获得的异或值

for bit from high downto 0:
  b = (x >> bit) & 1
  prefer = 1 - b
  if child[prefer] exists: ans |= 1 << bit

最大异或的贪心从高位开始，因为高位的 1 比所有低位加起来都更重要。

误区：按十进制大小找最大数即可得到最大异或。 异或大小由二进制位差异决定，最大数不一定产生最大异或。
误区：从低位开始贪心也可以。 高位权重大，必须优先保证高位尽量为 1。
误区：0-1 Trie 只适合字符串。 它存的是数字的二进制位路径，本质仍是按字符集为 {0,1} 的 Trie。
追问：为什么优先走相反 bit？ 相同 bit 异或为 0，相反 bit 异或为 1；想最大化当前位就走相反分支。
追问：复杂度是多少？ 若整数按 31 或 32 位处理，插入和查询都是 O(W)，总计 O(nW)。
追问：如何避免同一个数和自己配对？ 可以先查询已插入的数再插入当前数，或在节点维护计数控制。

八、一步步推演与边界

回答如何用 0-1 字典树（二进制 Trie）求数组中的最大异或对？时，最好额外走一遍小样例。先用 3～5 个元素演示正常操作，再故意加入空结构、单元素、重复值或极端位置，观察不变量是否仍成立。比如链表题要盯住前驱、当前、后继 3 个指针；树题要说明递归返回值代表什么；堆题要说明上浮/下沉什么时候停止；图题要说明 visited 或入度数组何时更新。

这种推演的价值在于把“我知道算法”变成“我能证明边界也不会错”。很多面试失分不是主流程不会，而是少了空节点、尾节点、重复边、环、K 越界这类边界。把这些点主动讲出来，既能减少代码 bug，也能让复杂度分析更可信。

边界类型	检查方式	容易出错的地方
空结构	输入为空或 root/head 为 null	直接访问属性导致异常
单元素	只有 1 个节点或元素	前驱/后继、左右子树判断错误
重复值	多个元素相等	比较条件写成 < 还是 <=
极端位置	头尾、最大最小、第一层最后一层	更新指针或索引越界

七、加强记忆

最大异或对用 0-1 Trie：把每个数按二进制位从高到低插入（只有 0/1 两分支）。求最大异或时逐位贪心走”相反”的分支（当前位 b 优先走 b^1，相异异或得 1，高位的 1 价值最大所以贪心正确），走不通才走相同位。把 O(n²) 暴力降到 O(n×32)。是「异或/位运算最值」问题的通用套路：按位建 Trie + 逐位贪心。

简化版

详细版