本课时有配套视频讲解，购买后即可观看（永久有效）
字典树
一、课上练习
编程练习
二、知识总结
✨ 核心思想
字典树（Trie，又称前缀树）是一种专门处理字符串集合的树形数据结构。它利用字符串的公共前缀来减少存储空间和查询时间。
Trie 的核心优势：
- 插入和查询的时间复杂度仅与字符串长度相关，为 O(|S|)，与集合大小无关
- 天然支持前缀匹配操作
- 可以扩展到01 Trie解决异或相关问题
✨ 算法原理
基本结构
Trie 是一棵多叉树：
- 根节点为空
- 每条边代表一个字符
- 从根到某节点的路径构成一个前缀
- 在单词结尾节点打标记
基本操作
插入字符串：从根出发，逐字符走，没有对应子节点就新建，最后在末尾打标记。
查询字符串是否存在：从根出发逐字符走，走不通或到达末尾无标记则不存在。
查询前缀：类似查询，但不需要末尾标记。
01 Trie
将整数的二进制表示从高位到低位插入 Trie。可以高效解决最大异或对等问题：对于每个数，在 Trie 中贪心地选择与当前位相反的分支，使异或值最大。
✨ 代码实现
基本字典树
字典树 - 字符串插入、查询、前缀匹配
1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 500005; // 最大节点数
5const int CHARSET = 26; // 字符集大小（小写字母）
6
7struct Trie {
8 int ch[MAXN][CHARSET]; // ch[p][c] = 节点p的第c个子节点编号
9 int cnt[MAXN]; // cnt[p] = 以节点p为结尾的字符串数量
10 int pre[MAXN]; // pre[p] = 经过节点p的字符串数量（前缀计数）
11 int tot = 0; // 节点计数
12
13 void init() {
14 tot = 0;
15 memset(ch[0], 0, sizeof(ch[0]));
16 cnt[0] = pre[0] = 0;
17 }
18
19 // 新建节点
20 int newNode() {
21 ++tot;
22 memset(ch[tot], 0, sizeof(ch[tot]));
23 cnt[tot] = pre[tot] = 0;
24 return tot;
25 }
26
27 // 插入字符串
28 void insert(const string &s) {
29 int p = 0;
30 for (char c : s) {
31 int id = c - 'a';
32 if (!ch[p][id]) {
33 ch[p][id] = newNode();
34 }
35 p = ch[p][id];
36 pre[p]++; // 经过此节点的字符串数+1
37 }
38 cnt[p]++; // 标记字符串结尾
39 }
40
41 // 查询字符串出现次数
42 int query(const string &s) {
43 int p = 0;
44 for (char c : s) {
45 int id = c - 'a';
46 if (!ch[p][id]) return 0;
47 p = ch[p][id];
48 }
49 return cnt[p];
50 }
51
52 // 查询以s为前缀的字符串数量
53 int queryPrefix(const string &s) {
54 int p = 0;
55 for (char c : s) {
56 int id = c - 'a';
57 if (!ch[p][id]) return 0;
58 p = ch[p][id];
59 }
60 return pre[p];
61 }
62
63 // 删除字符串（假设字符串确实存在）
64 void erase(const string &s) {
65 int p = 0;
66 for (char c : s) {
67 int id = c - 'a';
68 p = ch[p][id];
69 pre[p]--;
70 }
71 cnt[p]--;
72 }
73} trie;01 Trie 求最大异或对
01 Trie - 最大异或对
1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 100005;
5const int MAXBIT = 30; // 数值范围2^30
6
7struct Trie01 {
8 int ch[MAXN * 31][2]; // 每个节点只有0/1两个子节点
9 int tot = 0;
10
11 void init() {
12 tot = 0;
13 ch[0][0] = ch[0][1] = 0;
14 }
15
16 // 插入数x的二进制表示（从高位到低位）
17 void insert(int x) {
18 int p = 0;
19 for (int i = MAXBIT; i >= 0; i--) {
20 int bit = (x >> i) & 1;
21 if (!ch[p][bit]) {
22 ch[p][bit] = ++tot;
23 ch[tot][0] = ch[tot][1] = 0;
24 }
25 p = ch[p][bit];
26 }
27 }
28
29 // 查询与x异或值最大的结果
30 int queryMax(int x) {
31 int p = 0;
32 int res = 0;
33 for (int i = MAXBIT; i >= 0; i--) {
34 int bit = (x >> i) & 1;
35 int want = 1 - bit; // 贪心：希望走相反的位
36 if (ch[p][want]) {
37 res |= (1 << i);
38 p = ch[p][want];
39 } else {
40 p = ch[p][bit];
41 }
42 }
43 return res;
44 }
45} trie;
46
47int main() {
48 ios::sync_with_stdio(false);
49 cin.tie(nullptr);
50
51 int n;
52 cin >> n;
53
54 trie.init();
55 vector<int> a(n);
56 for (int i = 0; i < n; i++) {
57 cin >> a[i];
58 trie.insert(a[i]);
59 }
60
61 int ans = 0;
62 for (int i = 0; i < n; i++) {
63 ans = max(ans, trie.queryMax(a[i]));
64 }
65 cout << ans << "\n";
66
67 return 0;
68}✨ 执行示例
字符串 Trie 示例
插入字符串："apple", "app", "apply", "bat", "ball"
1root
2 / \
3 a b
4 | |
5 p a
6 | / \
7 p t l
8 / \ |
9 l l l
10 | |
11 e y- query("app") → cnt=1（"app" 存在）
- query("ap") → cnt=0（"ap" 不是完整单词）
- queryPrefix("app") → pre=3（"apple", "app", "apply" 共 3 个以 "app" 为前缀）
- queryPrefix("ba") → pre=2（"bat", "ball"）
01 Trie 求最大异或
数组 a = [3, 10, 5, 25, 2, 8]
查询 queryMax(5)（5 的二进制 = 00...00101）：
| 位（高→低） | 5 的该位 | 希望走 | 实际走 | 说明 |
|---|---|---|---|---|
| 第 4 位 | 0 | 1 | 1 | 25=11001 存在高位为 1 的路径 |
| 第 3 位 | 0 | 1 | 1 | 继续沿 25 的路径 |
| 第 2 位 | 1 | 0 | 0 | 25 的第 2 位为 0 |
| 第 1 位 | 0 | 1 | 0 | 没有匹配的路径，走 0 |
| 第 0 位 | 1 | 0 | 1 | 没有匹配的路径，走 1 |
5 XOR 25 = 00101 XOR 11001 = 11100 = 28，这是最大异或值。
✨ 解题步骤详解
Trie 的典型应用
1. 字符串查找与前缀统计
- 多模式匹配的基础（AC 自动机的底层结构就是 Trie）
- 统计前缀出现次数
2. 自动补全
- 输入前缀后，在 Trie 中 DFS 找到所有匹配的字符串
3. 最大异或对（01 Trie）
- 贪心从高位到低位选择相反的位
4. 异或前缀和 + 01 Trie
- 求子数组的最大异或和：用前缀异或和 + 01 Trie
子数组最大异或和
1// 利用前缀异或和：
2// subarray_xor(l, r) = prefix[r] ^ prefix[l-1]
3// 对于每个prefix[r]，在Trie中查找使异或最大的prefix[l-1]
4int maxSubarrayXor(int a[], int n) {
5 Trie01 trie;
6 trie.init();
7 trie.insert(0); // prefix[0] = 0
8
9 int prefix = 0, ans = 0;
10 for (int i = 1; i <= n; i++) {
11 prefix ^= a[i];
12 ans = max(ans, trie.queryMax(prefix));
13 trie.insert(prefix);
14 }
15 return ans;
16}5. 可持久化 Trie
- 结合可持久化技巧，支持查询任意区间内的最大异或
空间优化
Trie 的空间消耗较大（MAXN * CHARSET）。优化方法：
- 使用
map代替数组存储子节点（适用于字符集大的情况） - 动态开点，只在需要时分配节点
✨ 常见错误
- 节点数估算不足：n 个长度为 m 的字符串最多需要 n * m 个节点，不是 n 个。
- 忘记初始化新节点：新节点的 ch 数组、cnt、pre 必须清零。
- 字符映射错误：
c - 'a'只适用于全小写字母，大写或混合字符集需要调整。 - 01 Trie 位数设错：MAXBIT 应根据数据范围设定，如 10^9 需要 30 位。
- 删除操作不检查存在性：删除前应先确认字符串存在，否则 pre 和 cnt 会变负。
- 内存爆炸：字符集为 26 时每个节点 26 个指针，节点数 * 26 可能很大。注意 MAXN 的设定。
✨ 算法评价
| 操作 | 复杂度 |
|---|---|
| 插入字符串 | O(\ |
| 查询字符串 | O(\ |
| 前缀匹配 | O(\ |
| 最大异或查询 | O(log V)，V 为值域 |
| 空间复杂度 | O(总字符数 * 字符集大小) |
优点：
- 查询复杂度与集合大小无关，仅与字符串长度相关
- 天然支持前缀操作
- 01 Trie 高效解决异或问题
缺点：
- 空间消耗大（每个节点需要存储字符集大小个指针）
- 不如哈希表在简单查询上快（常数较大）
竞赛建议：字典树是字符串问题的基础数据结构，也是 AC 自动机的前置知识。01 Trie 在位运算相关题目中非常常见，务必熟练掌握。
三、课后练习
编程练习
- Phone List：L49934