Chapter 8 · Data Structures on Trees
Trie (Prefix Tree) and Its Relatives
Bitwise tries, binary tries for xor, suffix automaton neighbours, and the Aho–Corasick step up.
A rooted tree whose edges are labelled by alphabet symbols, such that each stored string is the label of a root-to-node path. Sharing prefixes is the entire point: total nodes ≤ total length of all strings + 1.
struct Trie {
static const int A = 26;
vector<array<int, A>> ch; vector<int> cnt;
Trie() : ch(1), cnt(1) {} // node 0 = root
void insert(const string& s) {
int v = 0;
for (char c : s) {
int x = c - 'a';
if (!ch[v][x]) { ch.push_back({}); cnt.push_back(0); ch[v][x] = (int)ch.size() - 1; }
v = ch[v][x]; cnt[v]++;
}
}
int count_prefix(const string& p) { // how many words start with p
int v = 0;
for (char c : p) { if (!ch[v][c - 'a']) return 0; v = ch[v][c - 'a']; }
return cnt[v];
}
};array<int,26> per node is 104 bytes; 106 nodes is 104 MB — over most limits. Three fixes, in order of preference:
- compress the alphabet: map symbols to [0,σ) first (letters → 26, digits → 10, or bits → 2),
map/unordered_mapper node: slower and worse memory unless the branching factor is genuinely ~1,- store edges in one flat array of
(node, char, child)sorted by(node,char)and walk with a pointer: cache-friendly and σ-free.
#The bitwise trie: max xor in O(30)
To maximise x ⊕ y over a set S, walk from the highest bit down and always take the child whose bit is ¬ of x's bit when it exists. This is optimal because the highest differing bit dominates: 2k > ∑i<k 2i.
struct Node { int ch[2]; };
vector<Node> t(1);
void insert(int x) {
int v = 0;
for (int i = 30; i >= 0; i--) {
int b = x >> i & 1;
if (!t[v].ch[b]) { t[v].ch[b] = (int)t.size(); t.push_back({}); }
v = t[v].ch[b];
}
}
int query(int x) { // max x ^ y over inserted y
int v = 0, res = 0;
for (int i = 30; i >= 0; i--) {
int b = x >> i & 1;
if (t[v].ch[b ^ 1]) { res |= 1 << i; v = t[v].ch[b ^ 1]; }
else v = t[v].ch[b];
}
return res;
}Applications that are "just" this: maximum xor subarray (insert prefix xors — al ⊕ … ⊕ ar is a prefix xor pair), maximum xor pair in a set, and with a persistent xor trie you get "max xor in a range [l,r]" in O(30) per query (CSES-style "XOR Queries" family).
#Autocomplete, deletion, and counts
The three bookkeeping rules
- store
cnt[v]= number of words passing through v, andend[v]= multiplicity of the word ending exactly here, - deletion = decrement along the path and optionally free the leaf-ward suffix — with
cntyou can prune empty subtrees so memory stays O(distinct prefixes), - prefix listing: DFS from the node of the prefix; output order is lexicographic for free, which is why tries sort strings in O(total length).
"Does any pattern occur in the text?" over many patterns needs Aho–Corasick: build the trie, add failure links (fail[v] = longest proper suffix of v's path that is a node — computed by BFS from the root, same recurrence as KMP's prefix function), then a single text scan gives all occurrences in O(|text| + ∑|patterns| + matches). "Longest repeated substring / distinct substrings" is suffix-array or suffix-automaton territory, not trie.