算法与AI · 知识点深化 · 算法思想
Trie 字典树与位运算技巧：前缀匹配与状态压缩
Trie（字典树）解决前缀匹配：自动补全、搜索提示。位运算用 & | ^ 做状态压缩和快速判断。这一页把这两个"小而美"的工具讲透。
① 怎么学（4 步走，约 65 分钟）
先建立直觉再抠细节，按这四步走最稳：
1看图建立直觉（10 分钟）
读②③：先在脑子里画出本课核心结构图。
2记完整体系（15 分钟）
读④：把对比表和公式看懂，不要急着背。
3跟例题走一遍（20 分钟）
精读⑤：看三个例题怎么用知识点解题。
4刷题纠错（剩余时间）
做⑦⑩，错题回⑥诊断。
本课小目标学完你要能：① 手写 Trie；② 前缀查询；③ 常用位运算技巧；④ 状态压缩。
② 一图看懂：Trie 与位运算
读法：中心是本课主题，四条分支展开核心维度，下方是典型应用与高频易错点。
③ 本质直觉：Trie 就是"共享前缀的树"
把 words ["apple","app","ban"] 存 Trie：根节点 a→p→p→l→e，"app" 共享前三个节点。查前缀 "ap" 直接沿 a→p 走，不用遍历所有词。
节点：children[26]（小写字母）或 Map，isEnd 标记词结束。
位运算：& 取位、| 置位、^ 翻转。n&(n-1) 消最低位 1，判断 2 的幂。
n & (n-1)消掉最低位的 1。判 2 的幂：n>0 且 n&(n-1)==0。统计 1 的个数反复消。
④ 完整知识体系
位运算常用技巧
| 操作 | 代码 | 用途 |
|---|
| 取第 i 位 | n & (1<| 判断某位 | |
| 置第 i 位 1 | n | (1<| 状态置位 | |
| 翻转第 i 位 | n ^ (1<| 切换状态 | |
| 消最低位 1 | n & (n-1) | 判 2 的幂/计数 |
| 高低位交换 | (n<<16)|(n>>16) | 位反转 |
Trie 插入for c: 子节点不存在则建; 走到尾 isEnd=true
Trie 查询for c: 子节点不存在返回 false; 走到尾看 isEnd
状态压缩
用一个 int 的 32 位表示 32 个开关。n|(1<<i) 打开，n&~(1<<i) 关闭。DFS 状态压缩 DP 常用。
⑤ 应用场景与例题
例1 插入 apple, app，查 ap
沿 a→p 走，存在。查 app 走 a→p→p 且 isEnd。
例2 判断 n 是不是 2 的幂
n>0 且 n&(n-1)==0。因为 2 的幂二进制只有一个 1。
例3 统计二进制 1 的个数
while(n){ count++; n&=n-1 }，消最低位 1。
做题心法Trie 共享前缀省空间，位运算比乘除快。
⑥ 高频错误诊断（4 条）
错误1：Trie 查询不查 isEnd查前缀和查完整单词不同：查单词要看 isEnd。
错误2：位运算优先级搞错& 比 == 低，要加括号。
错误3：n&(n-1) 判断忘记 n>0n=0 也满足，要排除。
错误4：Trie 用链表存 children用数组[26]或 Map，按字符走。
⑦ 考点真题演练（5 题）
考点分布
| 考法 | 出题形式 | 应对 |
|---|
| Trie | 问作用 | 前缀匹配 |
| 插入 | 问结构 | children 数组 |
| 位运算 | n&(n-1) 作用 | 消最低位1 |
| 2的幂 | 判断条件 | n>0且n&(n-1)==0 |
真题basic1. Trie 主要解决什么问题？
真题mid2. Trie 中标记一个词结束用？
真题mid3. n & (n-1) 的作用是？
真题hard4. 判断 n 是 2 的幂？
真题hard5. 状态压缩中用一个 int 表示什么？
⑧ 必背知识点卡
Trie：共享前缀树，children 数组
插入：逐字符走，尾标 isEnd
查询：查前缀不看 isEnd，查单词看
n&(n-1)：消最低位 1
2 的幂：n>0 且 n&(n-1)==0
置位：n|(1<
状态压缩：一个 int 存 32 个开关
⑨ 动手输出：写 Trie 插入和查询
场景：实现前缀树。
① 节点：children[26] + isEnd。
② 插入：逐字符走，不存在就建新节点。
③ 结尾：最后节点 isEnd=true。
④ 查询：逐字符走，断了就 false。
⑤ 前缀：走到尾不看 isEnd。
口述思路Trie 逐字符走，isEnd 区分单词和前缀。
⑩ 分层练习（基础 + 中档 + 拔高）
▍基础 6 题
基础2节点存什么？
children 和 isEnd。
基础4怎么置第 i 位？
n|(1<
基础52 的幂判断？
n>0 且 n&(n-1)==0。
基础6怎么清第 i 位？
n&~(1<
▍中档 5 题
中档1Trie 和哈希表区别？
Trie 支持前缀，哈希不支持。
中档2查单词和查前缀区别？
查单词要看 isEnd，前缀不看。
中档3统计 1 的个数？
while(n) count++, n&=n-1。
中档4为什么位运算快？
直接操作 CPU 指令，比乘除快。
中档5异或 ^ 用途？
翻转、找只出现一次的数。
▍拔高 5 题
拔高1Trie 内存优化？
节点多用数组或压缩。
拔高2位运算交换两数？
a^=b;b^=a;a^=b。
拔高5Trie 时间复杂度？
插入查询都是 O(L)，L 是词长。
⑪ 记忆口诀 + 7 天复习计划
三句口诀① Trie 共享前缀，children 走字符。② n&(n-1) 消最低位，判 2 的幂。③ 位运算状态压缩，一个 int 32 开关。
| 天 | 任务 | 自检 |
|---|
| 第 1 天 | 读②③，写 Trie 节点 | 结构对 |
| 第 2 天 | 背位运算表 + 基础 6 题 | 操作记住 |
| 第 3 天 | 做中档 5 题，写插入查询 | 代码对 |
| 第 4 天 | 做拔高 5 题，判 2 的幂 | 条件对 |
| 第 5 天 | 做⑦真题 5 题 | 限时每题 5 分钟 |
| 第 6-7 天 | 合书白板写 Trie | 不看资料 |
← 返回算法与AI总览