Patterns/Part III - Hashing & Auxiliary Structures/Trie XOR

Pattern Reference

Trie XOR

"Max XOR pair/subarray using binary trie. Properties of XOR on bits."

Loading...

Deep Dive Tutorial

Bitwise trie: each node has two children (bit=0, bit=1). Insert number by following its bit representation from MSB. Query max XOR with x: at each level, prefer the bit opposite to x's bit at that position (to maximize XOR). If not available, take the same bit. Maintain count at each node for "how many numbers have this prefix" — enables range XOR queries.

XOR trie with max query
class XORTrie {
    constructor(maxBit = 29) {
        this.maxBit = maxBit;
        this.trie = [[0, 0]]; // [left(0), right(1)] children (node indices)
        this.cnt = [0]; // count of numbers in subtree
    }

    insert(x) {
        let node = 0;
        for (let b = this.maxBit; b >= 0; b--) {
            const bit = (x >> b) & 1;
            if (!this.trie[node][bit]) {
                this.trie.push([0, 0]);
                this.cnt.push(0);
                this.trie[node][bit] = this.trie.length - 1;
            }
            node = this.trie[node][bit];
            this.cnt[node]++;
        }
    }

    // Maximum XOR achievable with query x
    queryMax(x) {
        let node = 0, result = 0;
        for (let b = this.maxBit; b >= 0; b--) {
            const bit = (x >> b) & 1;
            const want = 1 - bit; // opposite bit maximizes XOR
            if (this.trie[node][want]) {
                result |= 1 << b;
                node = this.trie[node][want];
            } else {
                node = this.trie[node][bit];
            }
        }
        return result;
    }

    // Count numbers with XOR ≤ k (range query)
    countXorAtMost(x, k) {
        let node = 0, count = 0;
        for (let b = this.maxBit; b >= 0; b--) {
            const xb = (x >> b) & 1, kb = (k >> b) & 1;
            if (kb === 1) {
                // All paths with xb⊕bit = 0 have XOR < current prefix, all valid
                const same = this.trie[node][xb];
                if (same) count += this.cnt[same];
                if (!this.trie[node][1 - xb]) return count;
                node = this.trie[node][1 - xb];
            } else {
                if (!this.trie[node][xb]) return count;
                node = this.trie[node][xb];
            }
        }
        return count + this.cnt[node];
    }
}

Worked Problems

1
Maximum XOR of Two Numbers in an Array
Medium
Solve ↗
2
Maximum XOR of Two Numbers in a Subarray
Hard
Solve ↗
3
Count Pairs With XOR in a Range
Hard
Solve ↗
⊕
Bitwise trie vs XOR basis:
- XOR basis: max XOR of any subset → O(30n), doesn't store individual numbers
- Bitwise trie: max XOR with one specific number, range XOR queries → O(30) per query

Key queries:
- Max XOR with x: greedily take opposite bit at each level
- Count XOR ≤ k: bit by bit, when k-bit=1, count all paths with XOR-bit=0 (those are smaller), then follow XOR-bit=1 path
- k-th smallest XOR: similar to count but find threshold

Persistent XOR trie: Store one version per prefix → answer "max XOR in subarray [l,r]" in O(30).
← All Patterns