Bitwise Trie for Max XOR

A bitwise trie stores integers instead of words. Each number is written from its highest bit to its lowest, so every node has only two children, 0 and 1, and the depth is fixed by the bit width. It answers "which stored number gives the largest XOR with x?" in time proportional to the number of bits.

The idea#

XOR gives a 1 exactly where two bits differ, and a higher bit is worth more than all the lower bits together. So to maximize x ^ y, decide greedily from the top bit down: at each level, go to the child with the opposite bit of x if it exists, because that sets this bit of the result to 1. Only if it doesn't exist, follow the same bit. No later choice can make up for a 0 in a higher position, which is why the greedy choice is safe.

If you know the word trie from Standard Trie, only three things change:

Property	Word trie	Bitwise trie
Children per node	up to 26 (or any alphabet)	2
Depth	length of the word	fixed: the bit width, such as 32
Query	follow the letter	prefer the opposite bit

How to spot it#

The word "XOR" plus "maximum" is the main cue.

"Maximum XOR of two numbers in the array."
"Maximum XOR of x with an element", sometimes with a limit on which elements are allowed.
Queries that add or remove numbers between XOR questions.

Template#

Insert each number from its highest bit down. Then ask the trie for the stored number that gives the largest XOR with a query x.

insert(x):
    node = root
    for i from B down to 0:            # highest bit first
        bit = bit i of x
        move node to its child for bit, creating it if missing
best_xor(x):
    node = root, result = 0
    for i from B down to 0:
        bit = bit i of x
        if node has a child for 1 - bit:   # opposite bit: XOR bit is 1
            set bit i of result
            node = that child
        else:
            node = child for bit
    return result

Each insert or query costs $O(B)$ for $B$ bits. Over $n$ numbers the whole run is $O(n \cdot B)$ . Insert a number before you query with it, so the trie is never empty. Pairing x with itself only gives 0, which never beats a real answer.

Pitfalls#

These mistakes cause the most wrong answers.

Walking from the low bit. The greedy choice only works from the highest bit down.
Too few bits. The trie must cover the largest value's highest bit. Walking positions 31 down to 0 is enough for any 32-bit non-negative value.
Querying an empty trie. Insert before you query, or skip the query for the first number.
The wrong set of numbers in the trie. Harder problems keep the same query and change which numbers are present when you ask. Control that set on purpose.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first one.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Maximum XOR of Two Numbers in an Array

For each number, insert it and then query its best partner. Keep the largest result. That covers every pair in $O(n \cdot B)$ .

Hint: Maximum XOR With an Element From Array

The allowed elements change per query. Sort the queries by their limit and sort the numbers. Before each query, insert numbers only up to its limit. Answering offline (reading all queries first, then answering them in your own order) keeps the trie correct for each query.

Hint: Maximum Genetic Difference Query

Numbers are inserted and removed. Keep a count in each node: increase it on insert, decrease it on removal, and treat a child with count 0 as missing. A DFS over the tree adds a node on the way down and removes it on the way back.

Key takeaways#

A bitwise trie has two children per node and a fixed depth equal to the bit width.
To maximize XOR, take the opposite bit whenever it exists, from the top bit down.
Each query or insert is $O(B)$ , so all pairs are covered in $O(n \cdot B)$ .
Counts in nodes support removal; sorting queries handles per-query limits.

Core idea#

A bitwise trie stores integers from the highest bit to the lowest. Each node has two children, 0 and 1. To maximize XOR with x, take the opposite bit at each level when it exists.

Key points#

XOR gives 1 where two bits differ.
A higher bit is worth more than all lower bits together. So the greedy choice from the top bit is safe.
If the opposite child is missing, follow the same bit.
Depth is fixed by the bit width, for example 32.
Each insert or query is $O(B)$ for $B$ bits. All pairs take $O(n \cdot B)$ .
Insert x before you query it. Pairing x with itself gives 0, which never beats a real answer.
Per-query limits: sort queries by limit and sort numbers. Insert numbers up to each limit, then answer offline.
Insert and remove: keep a count per node. A child with count 0 counts as missing.

Template#

insert(x):
    node = root
    for i from B down to 0:            # highest bit first
        move node to its child for bit i of x, creating it if missing
best_xor(x):
    node = root, result = 0
    for i from B down to 0:
        bit = bit i of x
        if node has a child for 1 - bit:   # opposite bit: XOR bit is 1
            set bit i of result; node = that child
        else:
            node = child for bit
    return result

Pitfalls#

Walking from the low bit. The greedy works only from the top.
Too few bits. Cover the largest value's highest bit.
Querying an empty trie.

Say it in an interview#

"From the top bit down, take the opposite bit whenever it exists."
"Each number costs O(B), so the total is O(n · B)."