作用

需要按字典序（或特定规律）存或运算一堆元素时，可以用这个来优化。这个树就像查字典一样。

示例

P1481. 魔族密码

这个是找前缀的字典树

#52. 「一本通 2.3 例 2」The XOR Largest Pair

这个是在插入时对比的字典树

实现

$trie$ 存整棵树，第一个是单词个数乘单词最长长度 $nt$^[1][2]，第二个是单词里字符的范围 $c$^[3]（比如 $26$ 个字母或 $10$ 个数字）。

$word$ 存树中第 $i$ 个组合是否为一个单词（$bool$）或这个单词有几个（$int$）。

$tot$ 存现在树已经建到第几个节点了。

以下代码是一个存小写字母的字典树以及其的插入函数。

int trie[N][26],word[N],tot;
void insert(string s){
    int u = 0;
    for (int i = 0;i < s.size();i++){
        int c = s[i] - 'a';
        if (!trie[u][c])    trie[u][c] = ++tot;
        u = trie[u][c];
    }
    word[u]++;
}

消耗

空间

树（$trie$）：$ntc$^{[1:1][2:1][3:1]}

单词（$word$）：$nt$^[1:2][2:2]。

时间

插入（$insert$）：$O(t)$^[2:3]。

查找（某个单词是否在树中）（$find$）：$O(t)$^[2:4]。

---

1. $n$ 为单词数 ↩︎ ↩︎ ↩︎

2. $t$ 为单词长度 ↩︎ ↩︎ ↩︎ ↩︎ ↩︎

3. $c$ 为不同单词个数 ↩︎ ↩︎