---
title: "Trie (Prefix Tree) and Its Relatives"
summary: Bitwise tries, binary tries for xor, suffix automaton neighbours, and the Aho–Corasick step up.
difficulty: core
tags: [trie, strings, xor]
time: total length
space: total length × alphabet
see: [advanced-tree/huffman, structures/sparse-table]
---

:::definition label="Trie"
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 $\le$ total length of all strings $+$ 1.
:::

```cpp trie.cpp
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];
    }
};
```

:::warning title="Memory is the constraint, not time"
`array<int,26>` per node is 104 bytes; $10^6$ nodes is 104 MB — over most limits. Three fixes, in order of preference:
1. **compress the alphabet**: map symbols to $[0,\sigma)$ first (letters → 26, digits → 10, or *bits* → 2),
2. `map`/`unordered_map` per node: slower and worse memory *unless* the branching factor is genuinely ~1,
3. store edges in one flat array of `(node, char, child)` sorted by `(node,char)` and walk with a pointer: cache-friendly and $\sigma$-free.
:::

## The bitwise trie: max xor in O(30)
:::idea title="Greedy on bits"
To maximise $x \oplus y$ over a set $S$, walk from the highest bit down and always take the child whose bit is $\neg$ of $x$'s bit when it exists. This is optimal because the highest differing bit dominates: $2^k > \sum_{i<k} 2^i$.
:::

```cpp xor-trie.cpp
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 — $a_l \oplus \dots \oplus a_r$ 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
:::props title="The three bookkeeping rules"
- store `cnt[v]` = number of words passing through $v$, and `end[v]` = multiplicity of the word ending exactly here,
- **deletion** = decrement along the path and optionally free the leaf-ward suffix — with `cnt` you can prune empty subtrees so memory stays $O(\text{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(\text{total length})$.
:::

:::example title="When a trie is the wrong tool"
"Does any pattern occur in the text?" over *many* patterns needs **Aho–Corasick**: build the trie, add failure links ($\operatorname{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{text}| + \sum|\text{patterns}| + \text{matches})$. "Longest repeated substring / distinct substrings" is suffix-array or suffix-automaton territory, not trie.
:::

:::figure src="Trie.svg" caption="Four words, seven nodes: the shared prefixes are the whole saving, and cnt[] on each node is what makes prefix queries O(|prefix|)."
:::

:::problems
- [[CSES 1731]] Word Combinations | https://cses.fi/problemset/task/1731 | core | trie + DP over prefixes
- [[CSES 1753]] String Matching | https://cses.fi/problemset/task/1753 | core | KMP / automaton, the trie's cousin
- [[CSES 2102]] Finding Patterns | https://cses.fi/problemset/task/2102 | hard | many patterns, many texts
:::