$\Huge\color{orchid}{点击此处获取更多干货}$

字典树（Trie）

计算机中异或运算是按位的，而异或的特点就是相同为0不同为1，那么对于两个数$x,y$，它们的二进制表示中数字不同的位数越多，$x~xor~y$的值越大，那么如何尽可能多的找到两个数二进制表示中不同的位数呢，这里就可以借助字典树实现
插值的时候要从被插入的数的二进制最高位开始，对应基数为$2^{30}$，为什么不是$2^{31}$那位，是因为$int$类型的整数，其二进制表示中从高到低的第一位是符号位，后面的31位才是数值位。对于所有的n个数，可以先把第一个数插入，然后从第二个数开始，先求前面每个数与它的最大异或值，然后把它插入。插值操作同时还可以保证，当查询到第$i$个数时，前面第$1到i-1$个数已经全部都在字典树里，能减少遍历次数

查询第$i$个数时，依旧是从最高位开始，从字典树的根节点开始寻找相反的数位代表的节点，然后在当前结果上乘2再加1，如果找不到相反的节点那就只能被迫进入相同数位的节点，只乘2不加1，最后一定可以得到最大的异或值，最终的结果就是所有查询结果的最大值，可以查一个就求一下

细节请见注释

C++ 代码

#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
using namespace std;

struct TrieNode {
    //一共就两个选择0和1，定长数组在析构的时候会自动被替换
    TrieNode* nxt[2];
    TrieNode() {
        nxt[0] = nxt[1] = nullptr;
    }
};

class Trie {
private:
    TrieNode* root;

    //析构函数中调用，按照二叉树后序遍历方式析构整个字典树，回收堆区内存
    void _delete(TrieNode* node) {
        if(!node) return;
        _delete(node->nxt[0]);
        _delete(node->nxt[1]);
        delete node;
    }
public:
    Trie() {
        root = new TrieNode;
    }

    //按照规范要自己管理堆区内存，笔试或面试中没有特殊要求可不回收
    ~Trie() {
        _delete(root);
    }

    //插值
    void insert(int num) {
        TrieNode* now = root;
        //由高向低
        for(int i = 30; i >= 0; i--) {
            //取得当前数位
            int bit = (num >> i) & 1;
            //没有节点就构造一个
            if(!now->nxt[bit]) now->nxt[bit] = new TrieNode;
            now = now->nxt[bit];
        }
    }

    //获取最大异或值
    int getMaxXor(int num) {
        TrieNode* now = root;
        int res = 0;
        //还是由高向低
        for(int i = 30; i >= 0; i--) {
            int bit = (num >> i) & 1;
            //优先取相反数位(xor 1)，没有就取相同数位
            if(now->nxt[bit ^ 1]) {
                res = 2 * res + 1;
                now = now->nxt[bit ^ 1];
            }
            else {
                res *= 2;
                now = now->nxt[bit];
            }
        }
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Trie trie;
    int n, x, ans = 0;
    cin >> n >> x;//输入第一个数时先不急着插入
    for(int i = 1;i < n;i++) {
        //从第二个数的输入开始，先把上一次输入的插入，然后再求当前输入的数与前面所有数的最大异或值
        trie.insert(x);
        cin >> x;
        ans = max(ans, trie.getMaxXor(x));
    }
    //最后一个数不插入也没影响
    //另外如果序列中只有一个数，那就直接输出0（自身异或的值）
    cout << ans << endl;
    return 0;
}