templates/binary-trie.cpp
compilable
$cat templates/binary-trie
Binary Trie
Trie on bit representation of integers — supports insert, erase, and XOR maximum query.
#binary-trie#xor#bit#trie#maximum-xor
Log in to track progress, save custom versions, and organize into collections.Log In
$cat source_code/
cpp
#include <bits/stdc++.h>
using namespace std;
const int LOG = 30;
struct BinaryTrie {
struct Node {
int ch[2];
int freq;
};
vector<Node> t;
BinaryTrie() { t.push_back({{0, 0}, 0}); }
int newNode() { t.push_back({{0, 0}, 0}); return t.size() - 1; }
void insert(int x) {
int cur = 0;
for (int b = LOG; b >= 0; b--) {
int bit = (x >> b) & 1;
if (!t[cur].ch[bit]) t[cur].ch[bit] = newNode();
cur = t[cur].ch[bit];
t[cur].freq++;
}
}
void erase(int x) {
if (!search(x)) return;
int cur = 0;
for (int b = LOG; b >= 0; b--) {
int bit = (x >> b) & 1;
int nxt = t[cur].ch[bit];
t[nxt].freq--;
if (t[nxt].freq == 0) { t[cur].ch[bit] = 0; return; }
cur = nxt;
}
}
bool search(int x) {
int cur = 0;
for (int b = LOG; b >= 0; b--) {
int bit = (x >> b) & 1;
if (!t[cur].ch[bit]) return false;
cur = t[cur].ch[bit];
}
return true;
}
int maxXor(int x) {
int cur = 0, res = 0;
for (int b = LOG; b >= 0; b--) {
int want = ((x >> b) & 1) ^ 1;
if (t[cur].ch[want]) { res |= (1 << b); cur = t[cur].ch[want]; }
else cur = t[cur].ch[want ^ 1];
}
return res;
}
};59 linesutf-8
$cat explanation_notes.md
notes_viewer --renderedmarkdown (math enabled)
Binary Trie
Stores integers as bit strings of fixed length . Each node has two children (bit 0 and bit 1), traversed from MSB to LSB.
Operations
insert(x) — add integer erase(x) — remove one occurrence of search(x) — check if existsmaxXor(x) — find element in trie that maximizes XOR Maximization
Greedily pick the opposite bit at each level. If the opposite child exists, take it (sets that bit in the XOR result). Otherwise, follow the same bit.
When to Use
Notes
LOG = 30 for int, use LOG = 62 for long long