企业官网建设流程全解析

这一周学的是数据结构选型。

同样的“字符串匹配”，有KMP、Trie、Rabin-Karp三条路；同样的“区间求和”，有前缀和、差分、树状数组、线段树四种结构。

它们不是“谁替代谁”的关系，而是各自在不同约束下最优：

Trie 赢在「前缀」 —— 查前缀O(L)，与词表规模无关 哈希 赢在「O(1) 比对」 —— 串相等判定从O(L) 降到O(1)，代价是概率性碰撞 树状数组 赢在「常数小」 —— 十几行代码、一个数组，够用时的最优解 线段树 赢在「通用」 —— 任意结合律聚合 + 区间修改，代价是4n空间

没有银弹，只有取舍。而“知道什么时候该选哪个”，正是这一周要给你的东西。

📊 本周六题结构对照表

一条隐藏主线：这六题里有四题都靠“复用已算过的信息”——Manacher复用镜像半径、Trie复用公共前缀、线段树复用整块区间、滚动哈希复用上一个窗口的指纹。
这条主线和KMP的next数组是同一条：已算过的信息，绝不再算第二遍。

🌳 字符串算法家族树

字符串问题 │ ┌─────────────────┼─────────────────┐ 单模式匹配 多模式/前缀 回文 │ │ │ ┌────┴────┐ ┌─────┴─────┐ │ KMP Rabin Trie AC 自动机 Manacher -Karp

怎么选？四句话：

1. 找一个模式串 →KMP（确定性最优）或Rabin-Karp（更好写）
2. 找一堆模式串 / 查前缀→Trie；要一次扫完文本命中所有模式 →AC自动机
3. 找回文→ 中心扩散（够用）或Manacher（加分）
4. 找重复子串 / 最长公共子串→滚动哈希 + 二分答案

📋 区间查询数据结构选型表（本篇最重要的一张表）

选型时只问三个问题：
① 数据变不变？
② 查的是区间还是前缀/最值？
③ 要不要区间修改？

三个决策点讲透：

1. 静态 vs 可变：静态就别上重型结构——前缀和O(1)查询是最优解
2. 能否用减法拆分：区间和 = 前缀差，树状数组够用；区间最值不能用减法撤销，必须上线段树
3. 单点改 vs 区间改：区间改只有线段树 + 懒标记能 O(logn)

一句话口诀：

静态查和用前缀，批量加减用差分；可变查和用树状，要最值或整段改才上线段。

📊 本周实测数据一览

三条比“谁更快”更重要的教训：

1. 量级碾压常数：Trie比HashSet慢 2.6倍看着很惨，但两者都是 O(n)，而暴力 O(n²)差的是25倍。先解决量级，再抠常数。
2. 平均快的，最坏可能崩：中心扩散在随机串上赢1.5倍，在全a串上输314倍。生产环境要防的是退化输入。
3. 常数会翻转结论：同样是O(n)，短窗口下切片比滚动哈希快。复杂度表决定上限，常数决定你在常规数据上到底赢不赢。

🎯 再加一条心法

今天补上最后一条——它正是这一周的结晶：

心法：数据结构选型先问三件事——数据变不变、查的是区间还是前缀、要不要整段修改

前八条心法解决的是“这道题怎么想”，第九条解决的是“这道题该装进什么结构”。

很多人一看到“区间求和”就写线段树，却没意识到数组是静态的，前缀和 O(1) 就能拿下；也有人死守前缀和，遇到数组可变就卡住。选错结构，代码写得再漂亮也是绕远路。

判断顺序固定为三步：先问变不变 → 再问查什么 → 最后问改不改区间。三步走完，答案基本就落在上面那张表里了。

九条心法速览

📊 全周总结表

每天一个算法，面试不再心虚。