你的进度
0/ 33 节已标记完成
下一节: 树状数组:区间、更新与前缀和
完成记录保存在此浏览器中。
这门课在网上
CSCI2740 笔记里的内容
数字只算这门课 33 节公开笔记里写了什么,不是网上已记录的关系。目前其中 0 节已细致地记录到网上。
在网上定理卡 97 · 定义 54 · 反例 50 · 概念视角 17 · 证明透视 47
第 1 章 · 5 节
区间查询
从存储区间的不变量推导 Fenwick 树的查询与更新,证明对数时间界,并区分增量、赋值及最小值查询。
- 1.1
树状数组:区间、更新与前缀和
从存储区间的不变量推导 Fenwick 树的查询与更新,证明对数时间界,并区分增量、赋值及最小值查询。
- 1.2
用线段树处理赋值与区间最小值
证明线段树的不变量,以及单点赋值下对数时间区间最小值查询。
- 1.3
线段树:结合式摘要与有序区间查询
推导结合式摘要的有序线段查询,并区分单点更新和延迟传播。
- 1.4
二维前缀和与矩形差分
推导四角求和查询和离线矩形加法,明确处理左闭右开边界、空矩形及预处理成本。
- 1.5
平方根分块:延迟加法与区间总和
区分存储值、延迟的整块加量与真实区块总和,证明可交错执行的区间加法及总和查询。
第 2 章 · 1 节
2. 静态区间查询
预处理二的幂长度区间以查询静态最小值。
- 2.1
静态区间最小值的稀疏表
证明二的幂长度区间不变量,解释重叠最小值查询。
第 3 章 · 1 节
图的连通性
无向多重图的 DFS low-link 与桥边。
- 3.1
无向多重图中的 DFS 桥边
保留平行边身份,证明 low-link 桥边判据。
第 4 章 · 1 节
区间更新
以端点差分处理区间加法与单点值。
- 4.1
差分数组与区间加法端点
证明离线区间加法的端点不变量,并联系 Fenwick 单点查询。
第 5 章 · 1 节
无偏游戏
有限正常玩法、mex 与异或。
- 5.1
无偏游戏的 mex 值与异或
证明有限无偏正常玩法游戏的异或法则,并跟踪取子游戏。
第 6 章 · 1 节
因数筛法
Möbius 因数和及互素配对计数。
- 6.1
Möbius 因数和与互素配对
证明因数指示式,并以倍数筛计算互素索引对。
第 7 章 · 1 节
带权区间调度
由相容前缀建立动态规划。
- 7.1
带权区间调度
推导带权区间的前驱递推、重建及复杂度。
第 8 章 · 3 节
计算几何
利用方向与有向面积判断点相对于凸多边形的位置。
- 8.1
有向面积与凸多边形中的点
运用叉积、边界测试与鞋带和,明确说明凸性及整数范围假设。
- 8.2
方向与闭线段相交
精确分类线段相交,包括共线和退化情形。
- 8.3
单调链凸包与共线点
构造凸包极点并证明按列分组的单调链算法。
第 9 章 · 2 节
字符串算法
利用边界和回退搜索重叠字符串。
- 9.1
KMP 字符串匹配:边界、回退与重叠匹配
从嵌套的边界推导前缀函数,证明模式串搜索的线性时间复杂度,保留重叠匹配,并由最长边界求最小周期。
- 9.2
Z 数组、区间复用与精确字符串匹配
证明前缀匹配复用的线性复杂度,并用 Z 值求精确匹配、边界与周期。
第 10 章 · 3 节
图搜索与连通性
低链值、桥边、有向分量与删点。
- 10.1
迭代低链值搜索与桥森林
追踪以边编号实现的迭代低链值计算,并构造由桥连接的森林。
- 10.2
强连通分量、完成顺序与缩点图
推导两遍有向 DFS 算法及其无环缩点图。
- 10.3
割点、DFS 根与删点后的连通分量数
推导 low-link 删点判据并计算剩余连通分量。
第 11 章 · 1 节
二进制快速幂
循环不变量、模幂与矩阵应用。
- 11.1
二进制快速幂:循环不变量、矩阵递推与游走计数
不靠交换律证明二进制快速幂并应用矩阵幂。
第 12 章 · 1 节
单调队列
窗口极值、支配关系与均摊成本。
- 12.1
滑动窗口最小值:支配、过期与单调双端队列
证明支配关系、处理重复值并界定双端队列总工作量。
第 13 章 · 2 节
轻重链剖分
树路径、子树大小与区间查询边界。
- 13.1
轻重链路径与查询边界
证明轻边数量界,并把顶点及边路径划分为区间查询。
- 13.2
祖先倍增、第 k 级祖先与最近公共祖先
复合父节点映射的二次幂,证明求最近公共祖先时的同步跳跃不变量,并在不虚构根以上祖先的前提下回答静态树查询。
第 14 章 · 2 节
子集动态规划
精确已访问集合状态、路径代价与最优路线。
- 14.1
子集状态、哈密顿回路与最优路线
推导精确已访问集合动态规划并还原最优有向回路。
- 14.2
递增子序列:最小尾值与有效见证
证明最小尾值不变量,处理相等值,并重建真正的子序列而不是把尾值数组当作见证。
第 17 章 · 2 节
数论
同余式、中国剩余定理与线性筛法。
- 17.1
精确算法:同余与几何定向
用扩展欧几里得算法解线性同余式,在模数不必互素时合并同余式,并为定向测试与模幂保持精确的边界检查。
- 17.2
线性筛:最小质因子与多次分解
证明合数的唯一生成规则,构造最小质因子表,并明确预处理、输出和算术运算的成本。
第 16 章 · 3 节
最短路径
含负环的 Bellman-Ford,以及使用双端队列的 0-1 BFS。
- 16.1
同步 Bellman–Ford:最短途径、负环,以及额外一轮所证明的内容
证明 Bellman-Ford 背后的限长递推式,把距离分为有限、无穷及负无穷,并说明额外一轮所能证明的内容。
- 16.2
0–1 BFS:为什么双端队列可以替代优先队列
当每条边的成本为 0 或 1 时,用双端队列计算最短距离,并证明双键不变量、处理过时条目及分析复杂度。
- 16.3
Dijkstra 与 Floyd–Warshall:单源与全点对最短路径
证明非负权重下的 Dijkstra 算法,指出负权边究竟在哪一步令它失效,并推导计算全点对距离的 Floyd–Warshall 递推式。
第 15 章 · 1 节
搜索与答案二分
对单调可行性判断进行二分搜索。
- 15.1
对容量进行二分搜索:先证明可行性检验
把最小化问题化为单调的是非判断,证明贪心可行性检验,并以安全的上下界与运算对答案进行二分搜索。
第 18 章 · 1 节
最小生成树
不相交集合、Kruskal 与 Prim,以及割性质。
- 18.1
不相交集合、Kruskal 算法与 Prim 算法
证明最小生成树的割性质,在不相交集合并查集上实现 Kruskal 算法,并与 Prim 算法比较。
第 19 章 · 1 节
贪心算法
区间调度与工作次序的交换论证。
- 19.1
贪心算法与交换论证:区间调度与最优工作次序
阐明贪心选择的证明模式,并以交换论证证明区间调度及按加权完成时间排序的贪心规则,同时说明为何看似合理的贪心规则会失败。