Binary Tries

A binary trie is an ordinary trie whose alphabet is {0, 1}. Insert each integer as its bits, most significant first, and every path from the root spells a bit prefix, so a node's existence answers "does any stored value start with these high bits?" in $O(1)$.

Node holds	C++	Python	Java
Two children	int child[2]	list of 2	int[] child
Whole trie, flat	vector<array<int, 2>>	one flat list	int[]
A level at once	unordered_set of prefixes	set of prefixes	HashSet

The structure exists for one question, which stored value makes the XOR with a given number as large as possible. Walk down from the top bit and at every level step toward the child holding the opposite bit if it exists. That greedy is safe because bit $b$ is worth $2^b$, more than every lower bit put together, so a high bit won now can never be paid back later. The usual slip is an off-by-one on the bit count, walking 30 levels when the values need 31.

Approach	Time	Extra space
Try every pair	$O(n^2)$	$O(1)$
Binary trie, one query	$O(31n)$	$O(31n)$
Binary trie, $q$ offline queries	$O(31(n + q))$ plus two sorts	$O(31n)$

Use one when a problem asks for the best XOR partner of a number, or for many numbers with a bound on which values may take part. If the bound is one-sided, sort the queries by it and let the trie grow as you go, the same offline trick as line sweep.

The problems below start with the maximum XOR pair over the whole array, and end with the same walk answered for many queries, each limited to the values at most its bound.