最大异或对字典树解决

字典树存放每个数得二进制编码，每个节点只有两个分支（0/1）
查询时候根据当前的二进制位，每次都向相反的方向延申，如果没有对应方向分支就顺着向下延申，这样最后得到尽可能大的异或数。
从前往后枚举，插入，查询。应该是从整个字典树里，a[]从头到尾查询。如果插入和查询同时进行，结果不一定是最大的。
查询：返回t t是和a[i]异或使得值最大的数，这个数事先存放在子典树里，在字典树里查询出来。最后和a[i]异或得到最大数。
u = k >> i & 1;从二进制首位开始向后查询

算法1

(字典树) $O(n)$

blablabla

时间复杂度

参考文献

基础课

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
/*最多十万个数，每个数最多三十一位，因此节点最多M个*/
const int N = 1e5, M = 31 * N + 1;
/*不要手误携程[M][N]会溢出*/
int trie[M][2], a[N], idx;

void insert(int k)
{
    int p = 0, u;
    /*根据二进制数中的每一位插入字典树,因为是int类型，每个数都是三十二位*/
    for(int i = 30; i >=0; --i)
    {
        u = k >> i & 1;
        if(!trie[p][u])trie[p][u] = ++idx;
        p = trie[p][u];
    }
}

int query(int k)
{
    int p = 0, u, m = 0;
    for(int i = 30; i >= 0; --i)
    {
        u = k >> i & 1;

        /*入如果当前位数的相反位存在，就向下延申*/
        if(trie[p][!u])
        {
            p = trie[p][!u];
            m = m * 2 + !u;
        }
        /*否则只能向当前位置延申*/
        else
        {
            p = trie[p][u];
            m = m * 2 + u;
        }
    }
    return m;
}
int main()
{
    int n, res; scanf("%d", &n);
    for(int i = 0; i < n; ++i)
    {
        scanf("%d", &a[i]);
        /*插入*/
        insert(a[i]);
    }
    for(int i = 0; i< n; ++i)
    {
         /*查询*/
       int num = query(a[i]);
       res = max(res, a[i] ^ num);
    }
    cout << res << " ";
    return 0;
}