算法刷题小结
这里整理刷题过程中反复出现的一些基础结构和常见套路，目标不是展开完整教程，而是把后续做题时最容易复用的判断方式先记下来。
1. 区间更新与查询
1.1 前缀和
适合频繁查询、不频繁更新的场景，典型问题是区间查询、单点更新。
- 维护一个前缀和数组。
- 查询时通过前缀和差值拿到区间结果。
- 时间复杂度：查询
O(1)，更新O(n)。
1.2 差分
适合频繁更新、不频繁查询的场景，典型问题是区间更新、单点查询。
- 维护一个差分数组。
- 更新时只改边界位置，最后再还原原数组。
- 时间复杂度：更新
O(1)，查询O(n)。
1.3 树状数组
适合频繁更新和查询的场景，常见形式是单点更新、区间查询。
- 本质是维护一个辅助数组，通过
lowbit做增量聚合。 - 代码量通常比线段树更小，适合处理基础动态前缀问题。
- 时间复杂度：更新和查询均为
O(log n)。
1.4 线段树
适合频繁更新和查询的场景，常见形式是单点更新、区间查询。
- 通过树形结构维护区间信息。
- 比树状数组更通用，适合处理更复杂的区间合并逻辑。
- 时间复杂度：更新和查询均为
O(log n)。 - 加上
Lazy Tag后可以支持区间更新，复杂度仍然保持在O(log n)。
2. 常见算法
2.1 二分查找
适合结果本身不容易直接求，但“给定答案后是否成立”比较容易验证的场景。核心是不断缩小搜索区间，找到目标值或满足条件的边界。
2.2 双指针
适合有序数组，或者需要同时遍历两个序列的场景。常见用途是寻找满足条件的元素对、压缩状态空间，或者维护左右边界。
2.3 滑动窗口
适合寻找满足条件的连续子序列。核心是维护一个动态区间，并在移动过程中更新窗口内的信息。
2.4 递归
适合需要枚举所有可能解的场景。
- 向下递归时可以携带当前路径信息。
- 向上回溯时可以基于整条路径做计算。
- 配合剪枝通常能显著减小搜索空间。
2.5 分治
适合当前问题可以拆成更小子问题，并且子问题结果能够高效合并的场景，例如归并排序、快速排序。
3. 进阶算法
3.1 单调栈
适合需要维护单调递增或单调递减序列的场景，很多题的关键是先判断是否存在局部单调性。时间复杂度通常是 O(n)。
3.2 贪心
适合每一步局部最优选择最终能推出全局最优解的场景。难点通常不在实现，而在于证明当前策略为什么成立。
3.3 动态规划
适合最优化问题。核心难点通常是：
- 根据题意定义状态。
- 找到状态转移关系。
- 处理边界条件和状态压缩。
很多题最后能不能做出来，关键就在于能不能先把状态设计对。
3.4 并查集
适合处理元素分组或连通关系问题，时间复杂度通常写作 O(alpha(n))。
- 用一个数组维护每个元素所属集合。
- 通过合并和查询处理连通性、分组归并等问题。
3.5 数学
常见内容包括排列组合、数论性质、构造、通过数学结论缩小搜索空间等。很多题表面像暴力，真正突破口在性质分析。
3.6 博弈
双人、状态有限、信息完全、没有随机性的博弈题，经常可以通过找必败态和必胜态来分析。
- 常见做法是先从最小状态举例，逐步往上推规律。
- 有些题还能用“先手窃取策略”做反证。
下面给一个两堆糖果的例子：
两人从两堆糖果中轮流取糖果，最后取走最后一颗的人获胜。每次只能从任意一堆中取任意数量，但不能同时从两堆取。
- 当状态是
(0, k)或(k, 0)时，当前玩家直接取完获胜。 - 当状态是
(1, 1)时，当前玩家无论取哪一堆，都会把状态交给对手的(0, 1)或(1, 0)，因此(1, 1)是必败态。 - 当状态是
(2, 2)时，当前玩家无论怎么取，都会把一个“不相等”的状态交给对手；对手总能再把状态调整回(1, 1)，因此(2, 2)也是必败态。 - 当状态是
(2, 3)时，当前玩家可以直接取成(2, 2)，把必败态交给对手，因此(2, 3)是必胜态。
继续往下推，可以发现：
- 两堆数量相等时，当前玩家处于必败态。
- 两堆数量不相等时，当前玩家总能把状态调整成相等，从而把必败态交给对手。