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

Representation	C++	Python	Java
Two children per node	int child[2]	list of 2	int[] child
Whole trie, flat	vector<array<int, 2>>	one flat list	int[]
One bit level at a time	unordered_set of prefixes	set of prefixes	HashSet

The structure is built to find 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 whenever it exists. That greedy choice is safe because bit $b$ is worth $2^b$, more than all lower bits combined, so winning a high bit now can never be beaten later. The usual slip is an off-by-one on the bit count, walking 30 levels when the input 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.