CC++ & Algorithm

01-Trie与异或极值问题

极难3
语言版本：通用
概述：01-Trie是一种专门处理二进制整数的高效数据结构，利用贪心思想在Trie上寻找最大异或值，常用于解决“最大异或对”等经典问题。

01-Trie：用二进制字典树快速找最大异或值

这是什么？用来解决什么问题？

想象一下，你和同学们玩一个“找最不同”的游戏。每人有一个代表自己性格的编号（比如用二进制数表示），你想找到和自己性格最相反的人——也就是二进制位上0和1差别最多的人。这个差别用异或（XOR）来衡量：两个数异或，对应位相同得0，不同得1。异或结果越大，说明两个人差异越大。

如果班上只有几个人，你一个个比较没问题；但如果全班有10万人，一个个比较就要花很多时间（O(N²)）。有没有更快的方法？答案就是 01-Trie（零一字典树）。

01-Trie是一种专门用来处理整数二进制位的数据结构。它把每个整数的二进制位看作一个字符串（每位只有0或1），然后插入到一棵二叉字典树中。因为整数最多只有31或63位（看是int还是long long），树的高度很浅，插入和查询都极快（O(bit)）。利用贪心思想，在查询与某个数异或最大的数时，每一步都尽量往与当前位相反的方向走，就能找到全局最大异或值。

生活中的比喻：找最“反着来”的朋友

假设全班同学的“性格编码”如下（用4位二进制简化）：

  • 小明：0010（2）
  • 小红：1010（10）
  • 小刚：0101（5）
  • 小丽：1100（12）

你想找和小明（0010）最不同的人。从最高位（第3位，从0开始）开始比较：

  • 小明最高位是0，你想找第3位是1的人（因为1和0异或得1，差异大）。查看所有同学，有小丽（1...）和小红（1...）满足。
  • 接着看第2位：小明是0，你想找一位上也是1的同学。小丽是1（1100）？不，小丽第2位是1？1100从高到低：1、1、0、0，第2位是1，对了！小红第2位是0（1010），所以第2位小丽更不同。
  • 继续下去，你最终会找到小丽（1100）和小明异或最大：0010 ^ 1100 = 1110（14）。

这个过程就是01-Trie的贪心查找：从高位开始，每一步都想走相反的位，如果不存在才走一样的。听起来像不像在字典里查单词？只不过这里每个“字母”只有0和1。

核心原理：01-Trie是什么？怎么用？

什么是01-Trie？

  • 它是一棵二叉树，每个节点最多有两个子节点，分别代表二进制位0和1。
  • 插入数字时，从最高位到最低位依次处理，高位靠近根节点。
  • 例如插入数字5（二进制0101），位宽假设4位（从第3位到第0位）：
    • 第3位：0 → 根节点走0分支
    • 第2位：1 → 走1分支
    • 第1位：0 → 走0分支
    • 第0位：1 → 走1分支，到达叶子（实际代码中不一定有叶子标记，但路径结束）。
  • 因为每个数字的二进制长度固定（比如31位），所以树的高度固定为31，非常浅。

异或的贪心性质

两个数异或，想让结果最大，就要让高位尽量不同。例如：

  0101 (5)
^ 1010 (10)
-----------
  1111 (15)

高位不同（0 vs 1）贡献了8（2³），而低位相同（0 vs 0）贡献0。所以高位差异比低位差异更重要。这就是贪心：从高位到低位，优先选择相反的位。

操作步骤（以查找与x异或最大的数为例）

  1. 插入阶段：将所有数字插入01-Trie，从高位到低位。
  2. 查询阶段：对于给定数字x，从根开始，遍历x的每一位（从高到低）：
    • 设当前位为bit（0或1），我们想走 want = 1 - bit 的相反分支。
    • 如果相反分支存在，就走向它，并且这一位的异或结果为1（给结果累加 1 << i）。
    • 如果相反分支不存在，只能走相同分支，异或结果为0。
  3. 走完所有位，就得到了最大异或值（或对应的那个数）。

时间复杂度

  • 插入和查询都是 O(bit)，bit 通常为31（int）或63（long long）。
  • 对于N个数字，总复杂度 O(N * bit)，远优于暴力 O(N²)。

常见的错误（新手容易踩的坑）

  1. 位宽选择错误：如果数字可能为负数（int的符号位），通常需要将数字转为无符号整型（unsigned int）或者处理32位（包括符号位）。题目若说非负整数，则用31位（0~30）足够。
  2. 忘记初始化子节点：在插入时，如果对应分支不存在，必须新建节点。C++中用 new 或数组实现时要注意初始化指针为nullptr。
  3. 查询时忘记判断分支是否存在：如果直接访问 cur->next[want] 而不检查是否为空，会导致程序崩溃或访问野指针。
  4. 位运算顺序搞错：从高到低遍历时，循环变量i要从最高位开始递减，例如 for i in range(MAX_BIT, -1, -1)。不要写反。
  5. 结果累加位置错误：只有在走了相反分支时，才对结果的该位置1。如果走了相同分支，该位保持0（因为异或相同为0）。
  6. 忽略“最大异或对”可能由同一个数组成：题目通常要求两个不同的数，但01-Trie查询时如果只插入一个数，查询自身会返回自身（因为相同分支一直存在），导致异或结果为0。实际应用中需要特殊处理，比如先查询再插入，或标记节点计数等。

完整代码示例（C++ 和 Python）

C++版本（详细注释）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 01-Trie节点，用数组表示两个子节点（0和1）
struct TrieNode {
    TrieNode* next[2];   // next[0] 指向0分支，next[1]指向1分支
    TrieNode() {
        next[0] = next[1] = nullptr;
    }
};

class OneZeroTrie {
private:
    TrieNode* root;
    static const int MAX_BIT = 30; // 假设数字范围0~2^31-1，用0~30共31位

public:
    OneZeroTrie() {
        root = new TrieNode();
    }

    // 插入一个数字num
    void insert(int num) {
        TrieNode* cur = root;
        for (int i = MAX_BIT; i >= 0; i--) {
            int bit = (num >> i) & 1;   // 取出第i位（从高到低）
            if (cur->next[bit] == nullptr) {
                cur->next[bit] = new TrieNode();
            }
            cur = cur->next[bit];
        }
    }

    // 查询与num异或的最大值（返回异或结果）
    int findMaxXor(int num) {
        TrieNode* cur = root;
        int res = 0;                    // 异或结果初始为0
        for (int i = MAX_BIT; i >= 0; i--) {
            int bit = (num >> i) & 1;   // 当前位
            int want = 1 - bit;         // 想要相反的位
            if (cur->next[want] != nullptr) {
                res |= (1 << i);         // 这位异或结果为1，累加
                cur = cur->next[want];
            } else {
                // 只能走相同位，异或结果为0，res不变
                cur = cur->next[bit];
            }
        }
        return res;
    }

    // 查询与num异或最大的那个数（而不是异或值）
    int findMaxXorNum(int num) {
        TrieNode* cur = root;
        int target = 0;                 // 目标数字初始为0
        for (int i = MAX_BIT; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int want = 1 - bit;
            if (cur->next[want] != nullptr) {
                target |= (want << i);   // 在目标数字的该位置want
                cur = cur->next[want];
            } else {
                target |= (bit << i);    // 只能走相同位
                cur = cur->next[bit];
            }
        }
        return target;
    }
};

int main() {
    // 假设全班同学的“性格编码”
    vector<int> nums = {3, 10, 5, 25, 2, 8};
    OneZeroTrie trie;

    // 插入所有数字
    for (int num : nums) {
        trie.insert(num);
    }

    // 找数组中两个数异或的最大值
    int maxXor = 0;
    for (int num : nums) {
        maxXor = max(maxXor, trie.findMaxXor(num));
    }
    cout << "数组中最大异或对的值: " << maxXor << endl;   // 期望输出 28 (25 xor 5 = 28)

    // 单独查询与某个数异或最大的数
    int x = 3;                         // 小明性格编码是3
    int partner = trie.findMaxXorNum(x);
    cout << "与 " << x << " 异或最大的数是 " << partner << "，异或值为 " << (x ^ partner) << endl;
    return 0;
}

Python版本（详细注释）

class TrieNode:
    def __init__(self):
        self.next = [None, None]   # 0和1分支

class OneZeroTrie:
    MAX_BIT = 30   # 31位，从30到0

    def __init__(self):
        self.root = TrieNode()

    def insert(self, num: int) -> None:
        """插入一个数字（非负整数）"""
        cur = self.root
        for i in range(self.MAX_BIT, -1, -1):   # 从高位到低位
            bit = (num >> i) & 1                # 取出第i位
            if cur.next[bit] is None:
                cur.next[bit] = TrieNode()
            cur = cur.next[bit]

    def find_max_xor(self, num: int) -> int:
        """返回与num异或的最大结果"""
        cur = self.root
        res = 0
        for i in range(self.MAX_BIT, -1, -1):
            bit = (num >> i) & 1
            want = 1 - bit                      # 想要的相反的位
            if cur.next[want] is not None:
                res |= (1 << i)                 # 这一位异或结果为1
                cur = cur.next[want]
            else:
                cur = cur.next[bit]             # 只能走相同位
        return res

    def find_max_xor_num(self, num: int) -> int:
        """返回与num异或最大的那个数本身"""
        cur = self.root
        target = 0
        for i in range(self.MAX_BIT, -1, -1):
            bit = (num >> i) & 1
            want = 1 - bit
            if cur.next[want] is not None:
                target |= (want << i)           # 在目标数字的该位置want
                cur = cur.next[want]
            else:
                target |= (bit << i)            # 只能走相同位
                cur = cur.next[bit]
        return target

if __name__ == "__main__":
    # 全班性格编码
    nums = [3, 10, 5, 25, 2, 8]
    trie = OneZeroTrie()
    for num in nums:
        trie.insert(num)

    # 找数组中最大异或对
    max_xor = 0
    for num in nums:
        max_xor = max(max_xor, trie.find_max_xor(num))
    print("数组中最大异或对的值:", max_xor)   # 28

    # 单独查询与小明的异或最大对象
    x = 3
    partner = trie.find_max_xor_num(x)
    print(f"与 {x} 异或最大的数是 {partner}，异或值为 {x ^ partner}")

总结要点

  1. 定义：01-Trie 是将整数的二进制位看作 0-1 字符串构建的二叉字典树，每个节点两个分支。
  2. 插入与查询：均从高位到低位，时间复杂度 O(bit)，通常为 O(31) 或 O(63)。
  3. 最大异或对：贪心思想，高位优先选择相反位，构造出的数字与给定数字异或最大。
  4. 应用：不仅限于最大异或对，还可以用于：
    • 子数组异或最大值（结合前缀异或）
    • 最小异或对（贪心改为走相同位）
    • 寻找最接近某个数的数字（按位贪心匹配）
    • 求解异或第K大等
  5. 注意：处理负数时需考虑符号位（32位），通常题目中数字非负；查询时避免同一个数与自己异或（可先查询再插入，或维护节点计数）。

掌握了 01-Trie，你就拥有了解决许多位运算问题的利器。比如 LeetCode 421（数组中两个数的最大异或值）、LeetCode 1707（与数组中元素的最大异或值）等。

下一节我们将学习 AC自动机，它将字典树和KMP结合起来，实现多模式串匹配——就像同时查找多个“性格”关键词一样高效。

例题精讲

1单选题

给定一个包含n个非负整数的数组，使用01-Trie求解最大异或对的时间复杂度是多少？

AO(n)
BO(n * log(max))
CO(n^2)
DO(n * log n)
2判断题

在使用 01-Trie 解决异或极值问题时，如果数组中包含负数，则无法直接使用 01-Trie。

3填空题
int queryMaxXor(Trie* root, int num) {\n    Trie* node = root;\n    int ans = 0;\n    for (int i = 31; i >= 0; i--) {\n        int bit = (num >> i) & 1;\n        if (node->child[!bit] != nullptr) {\n            ___(1)___;\n            node = node->child[!bit];\n        } else {\n            node = node->child[bit];\n        }\n    }\n    return ans;\n}
4单选题

以下哪个问题不能通过构造 01-Trie 并利用贪心策略高效解决？

A在数组中找出两个数，使得它们的异或值最大
B在数组中找出两个数，使得它们的异或值最小
C在数组中找出三个数，使得它们的异或值最大
D给定一个数 x，在数组中找出一个数使得与 x 的异或值最大
5填空题
void insert(Trie* root, int num) {\n    Trie* node = root;\n    for (int i = 31; i >= 0; i--) {\n        int bit = (num >> i) & 1;\n        if (node->child[bit] == nullptr) {\n            ___(2)___;\n        }\n        node = node->child[bit];\n    }\n}