Pattern Guide
Bitwise Trie (XOR Trie)
"Binary trie on bit representation. Find max XOR pair in O(n log MAX)."
A bitwise (XOR) trie stores integers bit by bit from MSB to LSB. For each number, insert its bits as a path from the root. To find the maximum XOR with a query value x: at each bit, try to take the opposite bit (maximizing XOR); if not available, take the same bit. O(n log MAX) total. Supports: max XOR pair, count integers with XOR ≤ k, online XOR queries.
Problems you can solve with this pattern
3 problems · click any to start solving
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];
}
}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.
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];
}
}- 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).