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
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#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