字典树（Trie）
字典树用于处理前缀相关查询。能以 O(单词长度) 的时间完成插入、查找、前缀统计，并天然支持自动补全、词频统计、最长公共前缀等操作。在算法竞赛中，Trie 是字符串处理的基础武器，尤其适合多模式匹配和大量字符串的集合维护。
字典树的思想
Trie 是一棵多叉树，每个结点代表一个字符，从根到该结点的路径拼起来即为一个前缀。根结点为空，每个结点拥有若干子结点，对应下一个字符。
cnt：经过该结点的单词数量（即以此为前缀的单词个数）
插入：从根开始，沿字符路径向下走，若某字符无对应子结点则新建，最后在结尾结点标记 is_end=True，同时沿途所有结点的 cnt++
查找单词：同样沿路径走，若中途缺失则不存在，否则检查最后结点的 is_end
样板
classTrie:
def__init__(self):
self.children = {}
self.cnt = 0# 经过该结点的单词数（前缀次数）
self.is_end = False# 是否有单词在此结束
definsert(self, word):
node = self
for ch in word:
if ch notin node.children:
node.children[ch] = Trie()
node = node.children[ch]
node.cnt += 1
node.is_end = True
defsearch(self, word):
node = self
for ch in word:
if ch notin node.children:
returnFalse
node = node.children[ch]
return node.is_end
defstarts_with(self, prefix):
node = self
for ch in prefix:
if ch notin node.children:
return0
node = node.children[ch]
return node.cnt
实例：
t = Trie()
words = ["apple", "app", "application", "appetite", "banana"]
for w in words:
t.insert(w)
print(t.search("apple")) # True
print(t.search("app")) # True
print(t.search("appl")) # False（前缀，不完整）
print(t.search("banana")) # True
print(t.starts_with("app")) # 4 (apple, app, application, appetite)
print(t.starts_with("appl")) # 2 (apple, application)
print(t.starts_with("ban")) # 1 (banana)
print(t.starts_with("cat")) # 0
关键点解读
children 用字典实现：通用性最好，支持任意字符集。对于仅小写字母的题目，可用长度为 26 的数组加速，children = [None]*26，并通过 ord(ch)-97 映射。数组版常数更小，但需要事先知道字符集大小。cnt 的作用：不仅用于前缀计数，还可用于删除操作，实现动态维护。is_end：区分“单词”与“前缀”。如果不需要区分可以省略。
复杂度分析
- 插入/查找/前缀检查：O(L)，L 为单词或前缀长度
- 空间：最坏情况下，每个结点存储一个字符，结点数 ≈ 所有单词的字符总数。插入 N 个单词，平均长度 L，则空间复杂度 。但只要单词间共享前缀，实际结点数远小于 。
典型应用场景
1. 单词集合维护（插入、删除、查询）
- 支持动态增删单词（删除时只需沿路径将
cnt 减 1，并将 is_end 置 False，可考虑回收无子结点）。
2. 前缀统计 & 自动补全
- 给定前缀，返回有多少单词以它为前缀：
starts_with(prefix) - 进一步可收集所有以某前缀开头的单词（需要遍历子树）。
3. 最长公共前缀
- 插入所有字符串后，从根开始向下走，只要当前结点只有一个子结点，就继续，遇到分支或结束则停止。
4. 词频统计（带权 Trie）
- 可以给每个结点增加一个
freq 字段，统计该前缀出现的总次数（例如搜索引擎的搜索词提示）。
5. 异或最大值问题（二进制 Trie）
- 将数字的二进制位（从高位到低位）插入 Trie，然后对每个数贪心走相反位寻找最大异或值。这是 Trie 在数字处理中的经典应用（如 LeetCode 421）。
6. 字符串排序
- 对 Trie 进行 DFS 即得到字典序排序结果（因为子结点有序时，先序遍历即排序）。
变种
1. 数组实现
当字符集为小写字母时，用列表代替字典可大幅提升效率：
classTrieArray:
def__init__(self):
self.children = [None]*26
self.cnt = 0
self.is_end = False
definsert(self, word):
node = self
for ch in word:
idx = ord(ch)-97
if node.children[idx] isNone:
node.children[idx] = TrieArray()
node = node.children[idx]
node.cnt += 1
node.is_end = True
2. 删除操作
defdelete(self, word):
node = self
path = []
for ch in word:
if ch notin node.children:
returnFalse
path.append((node, ch))
node = node.children[ch]
ifnot node.is_end:
returnFalse
node.is_end = False
# 逆向沿途减少 cnt，并删除无用的分支
for n, ch in reversed(path):
n.children[ch].cnt -= 1
if n.children[ch].cnt == 0:
del n.children[ch]
else:
break
returnTrue
3. 持久化 Trie
可持久化 Trie 用于处理区间异或等问题，是高级数据结构。
4. AC 自动机 = Trie + KMP 的失败指针
用于多模式串匹配，是 Trie 最重要的扩展之一。
练习题
入门：
LeetCode 208. 实现 Trie (前缀树)
LeetCode 720. 词典中最长的单词
洛谷 P2580 于是他错误的点名开始了（简单 Trie 统计）
前缀相关：
LeetCode 211. 添加与搜索单词 - 数据结构设计（支持通配符 '.'）
LeetCode 677. 键值映射（带权 Trie）
二进制 Trie（异或最值）：
LeetCode 421. 数组中两个数的最大异或值
洛谷 P4551 最长异或路径（树上前缀异或 + Trie）
进阶：
LeetCode 212. 单词搜索 II（Trie + DFS/回溯）
Codeforces 706D Vasiliy's Multiset（删除操作的二进制 Trie）
