【Trie树】最大异或对

题目

143. 最大异或对

---

在给定的 $N$ 个整数 $A_1，A_2……A_N$ 中选出两个进行 $xor$（异或）运算，得到的结果最大是多少？

输入格式

第一行输入一个整数 $N$。

第二行输入 $N$ 个整数 $A_1$～$A_N$。

输出格式

输出一个整数表示答案。

数据范围

$1 \le N \le 10^5$,
$0 \le A_i < 2^{31}$

输入样例：

3
1 2 3

输出样例：

3

解题

方法一：Trie 树

思路

把所有数字的二进制表示从高位开始创建为一棵 Trie 树 （每个节点的子节点只有 0 或者 1 两种选择），然后遍历所有数，在 Trie 树中查找尽可能每一位都与当前数字位相反的数（使得异或出来的数尽可能大），构造出异或结果并在遍历过程中维护一个最大的异或结果。

插入操作与普通 Trie 树大同小异，查询操作时，如果能找到与当前数字位相反的位节点就在异或结果中把该位标为 1 否则只能算作两位相同，把异或结果中的该位标为 0，比如：给定数字 $2, 4, 5, 12, 14$，构造出来一棵这样的树：

假如此时遍历到了 $5_{(10)}$，也就是 $0101_{(2)}$，对于每一位在 Trie 树中查找：

找出了 $1110_{(2)}$ 可以与 $0101_{(2)}$ 做异或取得「 $5_{(10)}$ 与其他数字做异或可以得到的最大值」： $1011_{(2)}$，注意：从上往下第三层时我们期望找到与 $1$ 相反的位 $0$，但是树中不存在 $0$ 的分支，所以只能退而求其次走 $1$ 的分支继续向下找了。

看了查找过程后我们就能发现在查找的过程中就可以构造异或结果，也就可以很方便地维护最大异或了。

Trie 树为什么要从高位开始构建而不是低位？
——因为要保证异或出的值尽可能大就应该保证异或出的数高位尽量大，所以在树中搜索的顺序就应该从高位开始，那么构建也应从高位开始。

代码

#include <iostream>

using namespace std;

const int N = 1e5 + 10, M = N * 31;
int sons[M][2], idx;
int n, ans;

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

int query(int x) {
    int p = 0, res = 0;
    for (int i = 30; i >= 0; --i) {
        int curr = x >> i & 1 ^ 1;
        res <<= 1;
        if (sons[p][curr] == 0) p = sons[p][curr ^ 1];
        else {
            p = sons[p][curr];
            ++res;
        }
    }
    return res;
}

int main() {
    scanf("%d", &n);
    while (n--) {
        int x;
        scanf("%d", &x);
        ans = max(ans, query(x));
        insert(x);
    }
    printf("%d\n", ans);
    
    return 0;
}

import java.util.*;	
import java.io.*;

public class Main {
    static final int N = (int) 1e5 + 10, M = N * 31;
    static int[][] sons = new int[M][2];
    static int idx = 0;
    
    static void insert(int x) {
        int p = 0;
        for (int i = 30; i >= 0; --i) {
            int curr = x >> i & 1;
            if (sons[p][curr] == 0) sons[p][curr] = ++idx;
            p = sons[p][curr];
        }
    }
    
    static int query(int x) {
        int p = 0, res = 0;
        for (int i = 30; i >= 0; --i) {
            int curr = x >> i & 1 ^ 1;
            res <<= 1;
            if (sons[p][curr] == 0) p = sons[p][curr ^ 1];
            else {
                p = sons[p][curr];
                ++res;
            }
        }
        return res;
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        int max = 0;
        while (n-- > 0) {
            in.nextToken();
            int curr = (int) in.nval;
            max = Math.max(max, query(curr));
            insert(curr);
        }
        System.out.println(max);
    }
}