vii. Binary Trie

A trie over the bits of integers, most significant bit first. Because a higher bit outweighs all lower bits together, XOR questions become greedy walks down the trie. With subtree counts it also answers order statistics and “count $y$ with $x\oplus y<K$”.

Implementation

struct BinaryTrie {
    static const int B = 30;
    vector<array<int, 2>> nx{{0, 0}}; vector<int> cnt{0};
    void add(int x, int d) {                       // d = +1 insert, -1 erase
        int v = 0; cnt[0] += d;
        for (int b = B - 1; b >= 0; b--) {
            int c = x >> b & 1;
            if (!nx[v][c]) nx[v][c] = sz(nx), nx.push_back({0, 0}), cnt.push_back(0);
            v = nx[v][c]; cnt[v] += d;
        }
    }
    int maxXor(int x) {                            // set must be non-empty
        int v = 0, r = 0;
        for (int b = B - 1; b >= 0; b--) {
            int c = (x >> b & 1) ^ 1;
            if (nx[v][c] && cnt[nx[v][c]]) r |= 1 << b, v = nx[v][c]; else v = nx[v][c ^ 1];
        }
        return r;
    }
    int countLess(int x, int K) {                  // # stored y with (x ^ y) < K
        int v = 0, res = 0;
        for (int b = B - 1; b >= 0 && v >= 0; b--) {
            int xb = x >> b & 1, kb = K >> b & 1;
            if (kb) { if (nx[v][xb]) res += cnt[nx[v][xb]]; v = nx[v][xb ^ 1] ? nx[v][xb ^ 1] : -1; }
            else v = nx[v][xb] ? nx[v][xb] : -1;
        }
        return res;
    }
};

Memory is $n\cdot B$ nodes. Preallocate when $n=2\cdot 10^5$ and $B=30$ (6 million nodes, about 72 MB as two int arrays plus counts).

Queries

Query	Walk
max $x\oplus y$	prefer the opposite bit

| min $x\oplus y$ | prefer the same bit |
| count $y$ with $x\oplus y<K$ | where $K$ has a 1, add the subtree that keeps the XOR bit at 0, and continue on the other side |
| $k$-th smallest $x\oplus y$ | descend comparing $k$ with the count on the preferred side |
| $k$-th smallest stored value, rank of $v$ | same walks with $x=0$ |
| max $x\oplus y$ with $y\le M$ | walk with a “tight to $M$” flag, like digit DP; or offline: sort queries by $M$ and insert values as $M$ grows |

Proof: the greedy max-XOR walk is optimal

By induction on bit position from most to least significant. At the top bit $b=B-1$: any $y$ achieving the opposite bit from $x$ there contributes $2^b$ to $x\oplus y$, and every lower bit together contributes at most ${\sum }_{i<b}{2}^i=2^b-1<2^b$ — so any $y$ with the opposite top bit beats every $y$ with the same top bit, regardless of what happens below. If the trie has a child on the opposite-bit side (nx[v][c] non-empty), taking it is therefore safe: the optimal answer is achieved by some element on that side. If it has no such child, every stored element agrees with $x$ on this bit, so the choice is forced and loses nothing. Having fixed the optimal top bit, the same argument applies recursively to the remaining $B-1$ bits among exactly the elements sharing the chosen top bit (the subtree the walk is now confined to), so by induction the greedy choice is optimal at every level. $■$

Proof: countLess correctly counts stored $y$ with $x\oplus y<K$

Process bits from most to least significant, maintaining the invariant that v (when $\ge 0$) is the trie node reached by following, for every processed bit, the child equal to $x$‘s bit at that position among the surviving candidates — i.e. the subtree of all stored $y$ that agree with $x$ on every bit processed so far. At a bit where $K$ has a 1: any $y$ whose corresponding XOR bit is 0 (i.e. $y$ matches $x$‘s bit, child nx[v][xb]) makes $x\oplus y$ strictly less than $K$ from this bit onward regardless of lower bits (same high-bit-dominance argument as above), so the whole subtree nx[v][xb] is counted immediately via cnt[...]; the walk then continues only among $y$ matching the opposite bit (XOR bit 1, tied with $K$‘s 1 so far), via nx[v][xb^1]. At a bit where $K$ has a 0: a $y$ with XOR bit 1 would make $x\oplus y>K$ from this bit (losing immediately), so only the XOR-bit-0 child (nx[v][xb]) can still tie $K$ and continue; nothing is added to res here. If v ever becomes $-1$ (no surviving candidates), the loop’s remaining iterations correctly add nothing. At the end, every stored $y$ has been classified as either counted (strictly below $K$ at the first bit it favourably differs) or excluded (tied throughout, giving $x\oplus y=K$, or decided against), so res is exactly $|\{y:x\oplus y<K\}|$. $■$

Classic problems

• Maximum XOR subarray: $\mathrm{xor}(l,r)=\mathrm{pref}[r+1]\oplus \mathrm{pref}[l]$; insert prefix XORs as you go, query each new prefix. $O(nB)$.
• Count subarrays with XOR $<K$ or in $[L,R]$: the same with countLess, $f(R+1)-f(L)$.
• $k$-th largest XOR among all pairs: binary-search-free descent over all $n$ elements simultaneously: keep for each $i$ its current trie node and decide each bit of the answer by summing the counts (CF 241B style), $O(nB)$.
• Max XOR of $x$ with an element of $a[l..r]$: persistent trie; version $r$ minus version $l-1$ via counts, or store the max index in each subtree and require it to be $\ge l$ in version $r$. $O(B)$ per query.
• Max XOR of $x$ with values in a subtree: Euler tour + persistent trie, or small-to-large merging of tries.
• Minimum spanning tree with weights $a_u\oplus a_v$ (Borůvka on a trie, or divide and conquer on the top bit): split by the highest bit, recurse on both halves, and connect them with one minimum-XOR edge found by walking one half’s elements in the other half’s trie. $O(nB\log n)$, or $O(nB)$ with care.
• Merging tries: merge two tries in time proportional to their common part, like segment tree merging. Small-to-large on tree subtrees.

Trie or basis?

“Choose one element” (or a pair) means the trie. “Choose any subset” means the XOR basis (XOR Basis). The trie stores elements and supports deletion and counting; the basis stores the span. They answer different questions: a trie is about the elements you inserted, a basis is about all XOR combinations of them.

	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)$