常见的一些小结
1. 各种更新/查询
- 前缀和:
- 适合频繁查询和不频繁更新的场景: 区间查询，单点更新。
- 维护一个前缀和数组，查询时通过前缀和差值实现高效查询。
- 时间复杂度：查询 O(1)，更新 O(n)。
- 差分：
- 适合频繁更新和不频繁查询的场景: 区间更新，单点查询。
- 维护一个差分数组，更新时通过差分数组实现高效更新。
- 时间复杂度：更新 O(1)，查询 O(n)。
- 树状数组：
- 适合频繁更新和查询的场景：单点更新，区间查询。
- 维护一个辅助数组，利用lowbit操作实现高效更新和查询。
- 时间复杂度：更新和查询均为 O(log n)。
- 线段树：
- 适合频繁更新和查询的场景：单点更新，区间查询。
- 维护一个树形结构，支持高效的区间操作。
- 时间复杂度：更新和查询均为 O(log n)。
- 加上Lazy Tag可以支持区间更新，时间复杂度仍为 O(log n)。
2. 常见算法
- 二分查找：
- 通常是直接难以求得结果，但是能较快验证结果的场景，通过不断缩小搜索范围来找到目标元素或满足条件的边界。
- 双指针：
- 适用于有序数组或需要同时遍历两个序列的场景，通过两个指针分别从不同方向遍历数组，寻找满足条件的元素对。
- 滑动窗口：
- 适用寻找满足条件的连续子序列的场景，通过维护一个窗口来动态调整子序列的范围，寻找满足条件的最优解。
- 递归：
- 有递有归，向下递归时可以获取到当前路径的信息，向上回溯可以根据这条路径的所有信息进行计算，
- 适用于需要枚举所有可能解的场景，可以结合部分条件剪枝。
- 分治算法：
- 可以将当前问题分解为更小的子问题，并且能够在处理完子问题后快速合并结果的场景，如归并排序、快速排序等。
3. 难一点的算法
- 单调栈：
- 适用于需要维护一个单调递增或单调递减序列的场景，时间复杂度 O(n)。
- 根据题目查看是否有局部单调性。
- 贪心算法：
- 每一步最优选择最后能得到全局最优解的场景，都比较难想。
- 动态规划：
- 最优化问题，最难的是根据题目找规律，从而设计状态并且进行计算状态转移方程。
- 很多题的状态需要根据题目进行部分变化，再进行设计。
- 并查集：
- 适用于需要处理元素分组或连接关系的场景，时间复杂度 O(α(n))。
- 通过维护一个数组来表示元素所属的集合，并提供合并和查询操作，适合解决一些与集合关系相关的问题，如连通性等。
- 数学：
- 博弈问题：
- 双人、状态有限、信息完全(无随机性)、不平局/双赢 的情况必有先手/后手必胜策略
- 上述情况可以举例找规律，并且有一个先手窃取后手使用反证法证明，先手必赢的方法，内容见漫士沉思录，下面例子从该视频学习。
- 例如，两人从两堆糖果轮流取糖果，最后取完最后一堆糖果的人获胜。每次可以从任意一堆取任意数量的糖果，但不能同时从两堆取。分析这个游戏的策略:
- 先考虑糖果数为(0,k) 或者(k,0) 的情况，先手直接取完获胜。
- 考虑糖果数为(1,1) 的情况，先手无论取哪堆糖果，都会让后手处于(0,1) 或者(1,0) 的情况，后手直接取完获胜。
- 考虑糖果数为(2,2) 的情况，先手无论取哪堆糖果，都会让后手处于(1,2) 或者(2,1) 的情况，后手必须取另一堆的1个糖果使情况变成(1,1)，否则先手直接取完获胜。(1,1)此时是后手必赢的情况。
- 考虑糖果数为(2,3) 的情况，先手取成(2, 2)，让后手处于(2,2) 的情况，使先手必赢。
- 以此类推，可以发现当两堆糖果数相等时，先手必赢；当两堆糖果数不相等时，后手必赢。策略是将糖果数量调整为相等的状态。