Wilson Wang王文轩

Algorithm handbook / C++17

算法讲义

以大一课件覆盖的算法为骨架，不只记住模板：先辨认问题结构，再理解不变量、复杂度与边界。 每篇讲义都包含可复制的 C++17 实现、示例推演和常见错误。

Notes
22
Topics
6
Language
C++17

内容由我重新组织和编写，并非课程原课件的转载；标为“延伸阅读”的部分用于建立知识联系，不代表课程逐项覆盖。

显示 22 篇讲义

01 / 5 notes

枚举与搜索

把状态空间写清楚，再用顺序、剪枝或双向扩展控制规模。

02 / 4 notes

算法设计

从单调性、局部选择和子问题结构中找到更快的解法。

基础O(n²)、O(n log n) 或 O(n + W)，取决于算法与值域

排序：从平方级到线性级

用循环不变量理解选择、插入、冒泡、归并、快速、计数、桶与基数排序，并根据数据规模和值域选择算法。

  • 排序
  • 分治
  • 计数
讲解与模板

03 / 4 notes

动态规划

明确状态、转移、初始化与遍历顺序，系统处理重叠子问题。

基础课程主线：0/1 与完全背包 O(nC)；延伸：多重背包 O(C · Σlog(cntᵢ+1))

背包 DP：0/1 与完全背包

用容量遍历方向控制物品使用次数，掌握 0/1 与完全背包，并在非课程主线的延伸中了解多重背包。

  • 动态规划
  • 背包
  • 空间优化
讲解与模板
进阶课程主线：LIS O(n²)、LCS O(nm)；延伸：LIS O(n log n)

子序列 DP：LIS 与 LCS

用“以当前位置结尾”和“双前缀”两类课程主线状态解决 LIS 与 LCS，并把 O(n log n) LIS 明确作为非课程主线延伸。

  • 动态规划
  • 子序列
  • LIS 与 LCS
讲解与模板

04 / 2 notes

字符串

利用前缀信息与哈希表示，避免重复比较字符。

05 / 2 notes

单调结构

维护不会回头的候选集合，把嵌套扫描降到线性时间。

基础时间 O(n)，空间 O(k)

单调队列：滑动窗口最值

用双端队列只保留仍在窗口内、且可能成为答案的候选下标，在线性时间内求出所有滑动窗口最大值。

  • 单调队列
  • 滑动窗口
  • 区间最值
  • C++17
讲解与模板

06 / 5 notes

区间数据结构

根据查询、修改与静态/动态约束，选择恰当的数据组织方式。

基础预处理 O(n log n)，查询 O(1)，空间 O(n log n)

ST 表：静态区间最值查询

利用倍增预处理所有 2 的幂长度区间，以两个可重叠区间在 O(1) 时间回答静态 RMQ，并说明幂等运算限制。

  • ST 表
  • Sparse Table
  • RMQ
  • 倍增
讲解与模板
基础单点修改与区间查询 O(log n)，空间 O(n)

树状数组：动态前缀和

从 lowbit 管辖区间理解树状数组，以单点增量、区间求和为主模板，并推导区间修改与单点或区间查询。

  • 树状数组
  • Fenwick Tree
  • 前缀和
  • lowbit
讲解与模板
进阶单次定位、插入与删除约 O(√n)，空间 O(n)

块状链表：用分块维护动态序列

把若干连续元素放进一个链表节点，以裂块和并块维持块大小，在数组搬移与链表遍历之间取得根号级折中。

  • 块状链表
  • Unrolled Linked List
  • 动态序列
  • 外存结构
讲解与模板