Как на бинарном боре найти максимальный XOR пары чисел из массива?

Числа кладём в бор как двоичные строки фиксированной длины (например 30 бит), старший бит — у корня. Чтобы максимизировать XOR с запрашиваемым числом, на каждом бите жадно пытаемся пойти в противоположный бит — тогда в этом разряде XOR даст 1, что весомее всех младших разрядов вместе.

struct XorTrie {
    static const int B = 30;
    vector<array<int,2>> t{{ -1,-1 }};
    void insert(int x) {
        int v = 0;
        for (int b = B; b >= 0; --b) {
            int bit = (x >> b) & 1;
            if (t[v][bit] == -1) { t[v][bit] = t.size(); t.push_back({-1,-1}); }
            v = t[v][bit];
        }
    }
    int query_max(int x) {                  // макс XOR x с числом из бора
        int v = 0, res = 0;
        for (int b = B; b >= 0; --b) {
            int bit = (x >> b) & 1;
            int want = bit ^ 1;             // хотим противоположный бит
            if (t[v][want] != -1) { res |= (1 << b); v = t[v][want]; }
            else v = t[v][bit];
        }
        return res;
    }
};

Алгоритм: вставляем все числа, для каждого a[i] спрашиваем query_max(a[i]), берём максимум. Время — O(n · B) = O(n·30), память — O(n·B). Жадность корректна, потому что старший установленный бит результата важнее любого набора младших.