形式化题目

给定 $N$ 个整数 $A_1, A_2, \dots, A_N$，其中 $1 \leqslant N \leqslant 10^5$，$0 \leqslant A_i < 2^{31}$。

求

即选出下标不同的两个数，使它们的按位异或值最大。数值可以相同，此时异或为 $0$。

正解

思路

朴素做法是枚举所有配对：

1
2
3
4ans = 0
for i in 1..N:
    for j in i+1..N:
        ans = max(ans, A[i] ^ A[j])

它在两两配对上做全扫描，$N = 10^5$ 时约 $5 \times 10^9$ 次异或，必然超时。瓶颈在于： 对每个 $A_i$，我们都在"和它配对的 $A_j$"这个维度上重扫一遍。可真正决定异或大小的 只是每个 $A_j$ 的高位形态——把高位形态组织成可复用的结构，就能让"谁与 $x$ 异或最大" 从一趟 $O(N)$ 扫描变成一次 $O(31)$ 的下降。

第一步，看高位。 比较两个异或结果的大小，就是从最高位逐位比较：

第 $k$ 位取 $1$ 的收益 $2^k$ 严格大于所有更低位的收益之和。所以"让高位尽量为 $1$" 永远优于"让所有低位都为 $1$"，最高位能被满足就一定先满足。

第二步，把数按位分层。 每个 $A_i$ 看成一条 31 位（第 $30$ 到第 $0$ 位）的 01 串， 按从高位到低位的顺序插入一棵二叉树——01 字典树。第 $i$ 层的分叉就是第 $i$ 位： 往左是 $0$，往右是 $1$。这样"以某个 01 前缀开头的所有数"恰好构成一个子树， 而"有没有一个数在第 $k$ 位与 $x$ 不同"就变成"那棵子树在不在"。

第三步，贪心下降。 查询"谁与 $x$ 异或最大"时从根出发，对第 $k$ 位：

• 若"反向边"（该位与 $x$ 相反）的子树存在，就走过去——这一位异或为 $1$， 收益 $2^k$ 已经锁定；由第一步，这不可能被任何"该位为 $0$"的候选反超；
• 否则只能走同向边——该位异或只能为 $0$，但这批数全都如此，没得选。

每一步之后，剩下的决策都落在刚走进的子树里，问题规模缩小一位，所以逐位贪心是独立决策的。

第四步，先全插后全查。 把 $N$ 个数全部插入，再对每个 $x$ 查一次、取最大值。贪心下降的终点 是一条真实的根到叶路径，对应某个实际插入过的 $A_j$，所以每次查询的结果都对应一个真实可达的配对， 不会高估；反过来取到最优配对 $(A_i, A_j)$ 时，查询 $A_i$ 至少能得到 $A_i \oplus A_j$，不会低估。 允许 $y = x$（异或 $0$）不影响最大值，而 $N = 1$ 时树上只有一条路径、结果自然为 $0$。

以样例 $A = [2, 9, 5, 7, 0]$ 为例，把每个数只保留低 5 位以便在一屏内看清：

插入后得到的 01 字典树如下，内部结点是前缀，叶子（标 =值）是真实元素：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16root
└─ 0
   ├─ 0
   │  ├─ 0
   │  │  ├─ 0
   │  │  │  └─ 0   (=0)
   │  │  └─ 1
   │  │     └─ 0   (=2)
   │  └─ 1
   │     ├─ 0
   │     │  └─ 1   (=5)
   │     └─ 1
   │        └─ 1   (=7)
   └─ 1
      └─ 0
         └─ 1   (=9)

查询 $x = 9$（01001）的逐位决策正是样例答案的来源：

最终落在 $A_j = 7$ 上，$9 \oplus 7 = 1110_2 = 14$。5 个元素的查询结果分别是 $11, 14, 12, 14, 9$（如 $x = 2$ 时得到 $2 \oplus 9 = 11$），最大值 $14$ 与样例输出一致。

实现要点：结点上界是 $1 + 31N \approx 3.1 \times 10^6$（$N = 10^5$）。若每个结点写成 [0, 0] 列表，光对象头加指针就要超过 200 MB，会顶破 128 MB 限制；因此用 array('i') 把两个 int32 孩子槽平坦存在 ch[2u]、ch[2u+1]，只要约 25 MB。根固定占用下标 $1$， 槽值 $0$ 就永远可以安全地表示"这条边不存在"，省掉额外的标记数组。

补充：这类"最大异或"还有一个等价的位前缀集合做法——从高位到低位维护 $\{A_i \text{ 的高位前缀}\}$ 集合，尝试把答案的这一位置 $1$ 并检查是否有两个前缀 互为"目标异或"。它与 01 字典树同为 $O(31N)$，只是用集合换掉了树的下降。 本题出自字典树章节，正文给出树上的贪心实现。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 13:05
# update_at: 2026-09-30 13:05

import sys
from array import array

TOP_BIT = 30  # A_i < 2^31，二进制最高位是第 30 位
ABSENT = 0    # 孩子槽为 0 表示这条边不存在；根固定在下标 1，槽 0 永远空着


def insert(ch: array, x: int) -> None:
    """把 x 的 31 位从高到低插入 01 字典树，缺哪条边就新建哪个节点。"""
    u = 1
    for bit in range(TOP_BIT, -1, -1):
        b = x >> bit & 1
        v = ch[u * 2 + b]
        if v == ABSENT:
            v = len(ch) >> 1          # 两槽一对（下标 2u、2u+1），下一对就是新节点号
            ch.extend((0, 0))
            ch[u * 2 + b] = v
        u = v


def best_xor(ch: array, x: int) -> int:
    """在树上贪心取与 x 异或最大的已插入值：每位优先走与 x 相反的那条边。"""
    u, res = 1, 0
    for bit in range(TOP_BIT, -1, -1):
        b = x >> bit & 1
        v = ch[u * 2 + (b ^ 1)]
        if v == ABSENT:               # 没有相反位可走，只能将就走相同位（该位异或为 0）
            u = ch[u * 2 + b]
        else:
            u = v
            res |= 1 << bit           # 这一位成功取反，对答案贡献 2^bit
    return res


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    nums = [next(data) for _ in range(n)]

    ch = array('i', [0, 0, 0, 0])     # int32 平坦数组：0 号空槽 + 1 号根节点
    for x in nums:
        insert(ch, x)

    # 贪心走到的叶子一定是真实插入过的元素，所以 best_xor 的值总能作为某个配对达成；
    # 自己配自己只会得到 0，不会抬高最大值。
    print(max(best_xor(ch, x) for x in nums))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 03:07
 * update_at: 2026-10-05 03:07
 */
// main.cpp：01 字典树求最大异或对，先全部插入再逐个贪心查询，O(31N)。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int TOP_BIT = 30;            // A_i < 2^31，二进制最高位是第 30 位
const int MAXNODE = 31 * MAXN + 5; // 每个数最多新建 31 个节点，再加一个根节点

typedef long long ll;

ll n;
ll a[MAXN]; // 输入的 N 个整数

// 01 字典树：ch[u][b] 表示从节点 u 走"第 b 位"这条边能到的孩子，0 表示这条边不存在
int ch[MAXNODE][2];
int node_cnt = 1; // 已分配的节点编号，根固定为 1，节点 0 永远空着

// 把 x 的 31 位从高位到低位插入 01 字典树，缺哪条边就新建哪个节点。
void insert_number(ll x) {
    int u = 1;
    for (int bit = TOP_BIT; bit >= 0; bit--) {
        int b = (x >> bit) & 1;
        if (ch[u][b] == 0) {
            node_cnt++;
            ch[u][b] = node_cnt;
        }
        u = ch[u][b];
    }
}

// 在树上贪心求与 x 异或最大的已插入值：每一位优先走和 x 相反的那条边。
ll best_xor(ll x) {
    int u = 1;
    ll res = 0;
    for (int bit = TOP_BIT; bit >= 0; bit--) {
        int b = (x >> bit) & 1;
        int opposite = ch[u][b ^ 1];
        if (opposite != 0) { // 相反位存在，这一位异或取 1，收益 2^bit 大于所有低位之和
            u = opposite;
            res |= 1LL << bit;
        } else { // 没有相反位可走，只能将就走相同位，这一位异或为 0
            u = ch[u][b];
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        insert_number(a[i]); // 先把所有数插入，再逐个查询
    }

    // 贪心下降的终点一定是真实插入过的数，所以每次查询的结果都能由某个真实配对达成；
    // 自己和自己配对只会得到 0，不会抬高最大值。
    ll ans = 0;
    for (ll i = 1; i <= n; i++) {
        ll value = best_xor(a[i]);
        if (ans < value) {
            ans = value;
        }
    }
    cout << ans << "\n";

    return 0;
}

复杂度

• 时间复杂度：$O(31N)$。插入与查询各走 31 层，$N = 10^5$ 时约 $6.2 \times 10^6$ 次循环迭代 （暴力配对约 $N^2/2 \approx 5 \times 10^9$ 次，是这个量的约 1600 倍）。与标准 C++ 正解同阶。
• 空间复杂度：$O(31N)$，即 $1 + 31N$ 个结点。平坦 array('i') 实现约 $25$ MB， 在 128 MB 限制内。

图示解析

从"选两个数"到"树上贪心"的完整路线：

1
2
3
4
5
6
7
8
9
10
11
12
13输入 N 个整数 (A_i < 2^31)
        │
        │  第 k 位收益 2^k > 所有低位收益之和
        ▼
最大异或 = 高位优先 → 从第 30 位往第 0 位逐位决定
        │
        │  每位的选择只依赖"某个 01 前缀是否出现"
        ▼
把每个数按 30→0 插入 01 字典树（子树 = 前缀集合）
        │
        │  查询 x：每层优先走与 x 相反的孩子
        ▼
对每个 x 取 best_xor(x)，ans = max(...)

这个路线图只保留四个关键节点：高位优先给出"逐位决定"的可行性； 前缀集合给出可复用的数据结构；贪心下降给出单次 $O(31)$ 的查询； 最后的 max 把"配对"问题拆成了 $N$ 个独立的单点查询。

总结

• 最大异或对的本质是高位优先后逐位决策：第 $k$ 位的 $2^k$ 大于所有低位之和， 所以能取 $1$ 就一定取 $1$。
• 01 字典树是承载"某位取反是否可行"的自然结构：一条从根到叶的路径就是一个数， 一棵子树就是"某个 01 前缀"的全部数。
• 单次查询 $O(31)$，乘上 $N$ 次查询得到 $O(31N)$；贪心落点必是真实元素， 所以"先全插后全查、取最大值"就是答案。
• 结点数上界 $31N + 1$：用 int32 平坦数组（array('i')，两槽一对）把空间压到约 25 MB； 若用列表套列表表示结点会超出 128 MB。
• 同类题型：$A_i$ 范围决定层数；while x 式的有效位截断会在 $x = 0$ 时出错， 固定 $30 \to 0$ 的 31 层最稳。