Binary Trie

A trie over the bits of integers, most significant first. It turns XOR problems into greedy walks, and it is one of the highest-value structures to have memorised.

Implementation

struct BinaryTrie {
    static const int B = 30;                        // bits, adjust for the value range
    vector<array<int,2>> nxt;
    vector<int> cnt;
 
    BinaryTrie() { newNode(); }
    int newNode() { nxt.push_back({-1,-1}); cnt.push_back(0); return nxt.size()-1; }
 
    void insert(int x, int delta = 1) {
        int v = 0;
        for (int b = B - 1; b >= 0; b--) {
            int c = (x >> b) & 1;
            if (nxt[v][c] == -1) nxt[v][c] = newNode();
            v = nxt[v][c];
            cnt[v] += delta;
        }
    }
    void erase(int x) { insert(x, -1); }
 
    int maxXor(int x) {                             // max of x ^ y over stored y
        int v = 0, res = 0;
        for (int b = B - 1; b >= 0; b--) {
            int c = (x >> b) & 1;
            int want = c ^ 1;                       // prefer the opposite bit
            if (nxt[v][want] != -1 && cnt[nxt[v][want]] > 0) { res |= 1 << b; v = nxt[v][want]; }
            else v = nxt[v][c];
        }
        return res;
    }
};

cnt makes deletion possible (decrement rather than unlink), which is what enables sliding-window and offline variants.

The greedy is optimal

At the most significant bit, setting it beats everything the lower bits could contribute: $2^b>{\sum }_{i<b}{2}^i$. So taking the opposite bit whenever a subtree exists is provably optimal — no backtracking needed.

What it answers

Query	Method
Maximum $x\oplus y$ over stored $y$	greedy opposite-bit walk
Minimum $x\oplus y$	greedy same-bit walk
Count stored $y$ with $x\oplus y<K$	walk; when $K$‘s bit is 1, add the whole subtree matching 0 and descend the other
Count stored $y$ with $x\oplus y\ge K$	total minus the above
$k$-th smallest value of $x\oplus y$	descend using subtree counts
$k$-th smallest stored value	same walk with $x=0$
Count values $<v$	subtree counts

The classic problems

Maximum XOR subarray

$\mathrm{xor}(l,r)=\mathrm{pref}[r+1]\oplus \mathrm{pref}[l]$. Insert prefix XORs one at a time and query the maximum against each new prefix:

BinaryTrie t; t.insert(0);
int cur = 0, best = 0;
for (int x : a) {
    cur ^= x;
    best = max(best, t.maxXor(cur));
    t.insert(cur);
}

$O(n\cdot B)$ — the standard solution, and a good template for the whole family.

Maximum XOR pair in an array

Insert everything, then query each element. $O(nB)$.

Count subarrays with XOR in $[L,R]$

$f(K)=$ count of subarrays with XOR $<K$, answered by the “count less than” walk; the answer is $f(R+1)-f(L)$.

Maximum XOR with a range constraint ($y\le M$)

Walk both the query and the bound simultaneously, tracking whether the prefix is already strictly below $M$ — the same tight flag idea as digit DP.

Persistent binary trie

Make it persistent and you can answer “maximum XOR of $x$ with any element in the index range $[l,r]$”: build version $i$ after inserting the first $i$ elements, then query with subtree counts differenced between versions $r$ and $l-1$.

$O(nB)$ memory, $O(B)$ per query. This is the standard solution to a whole class of otherwise-hard problems.

Binary trie vs XOR basis

	Binary trie	XOR basis
Stores	a multiset of values	a linear span
Max XOR with a query $x$	$O(B)$	$O(B)$
Max XOR over all subsets	✘	✔
Count values with a property	✔	✘
$k$-th smallest	✔	✔ (over the span)
Deletion	✔	hard
Memory	$O(nB)$	$O(B)$

They answer different questions: a trie is about the elements you inserted, a basis is about all XOR combinations of them. Problems saying “choose a subset” want the basis; problems saying “choose an element” want the trie.

See also: Trie · Linear Basis · Bit Manipulation