基础算法系列 · 总纲

1. 分讲总表

难度层：J = CSP-J 复赛够用；J⭐ = J 组进阶；S = CSP-S 复赛必备；S⭐ = S 组进阶。

#	标题	一句话	大纲	层	主要例题	状态
00	总纲（本文）	边界、大纲对应、写作约定	—	—	—	✅
01	前缀和与差分	花 $O(n)$ 预处理，把每次操作压到 $O(1)$；两者互为逆运算	未单列（真题高频）	J	P8218、P2367、P3397、P2004、P1115、P4552	✅ `01-prefix-sum-difference.md`（2026-09-04 从顶层迁入）
02	二分查找与二分答案	不知道答案是多少，但给你一个答案你能验证	【4】二分法	J⭐	P2440、P2678、P3853、P1902、P4343、P1024、P3382	✅ `02-binary-search.md`
03	排序的应用与贪心	比较器、多关键字，以及”怎么证明这个贪心是对的”	【3】贪心法、【3~6】排序	J	P1223、P2240、P1803、P1094、P2949	✅ `03-sorting-and-greedy.md`
04	枚举、模拟与构造	J 组 T1/T2 的全部；子集枚举与状态编码	【1】枚举法、【1】模拟法	J	P7909、P11228、P5660、P1003、P2141、P2036、P9748、P14358	✅ `04-enumeration-simulation-construction.md`
05	搜索（一）：回溯与剪枝	选择 → 递归 → 撤销；三类剪枝 + 搜索顺序也是剪枝	【6】搜索的剪枝优化	J⭐	P1219、P1706、P1036、P2404、P2392、P1088、P1731、P1092	✅ `05-backtracking-and-pruning.md`
06	搜索（二）：迭代加深、双向、折半	指数级搜索的三种压缩手段	【7】迭代加深、【7】双向广搜、【7】启发式搜索	S⭐	P1763、P2324、P2534、P1032、P4799、P3067、P5691	✅ `06-iddfs-bidirectional-mitm.md`
07	双指针与滑动窗口	两个指针都只往一个方向走	大纲未单列	J⭐（初赛为主）	P1147、P1638、P1381、P1102、P1886、P1440、P2564、⭐P7915	✅ `07-two-pointers.md`
08	分治	主定理，以及分治的建模视角	【6】分治算法、【5】归并/快排	S	P1115、P1923、P1908、P1257、P1429、⭐⭐P11234	✅ `08-divide-and-conquer.md`

为什么没有”倍增”独立一讲：ds-series/07（ST 表 = 序列上的倍增）与 graph-series/12（LCA 倍增）已经从两个方向讲透了，math-series/01（快速幂）是第三个。三处已经互相印证，再单开一讲只会重复；本线第 00 讲的知识地图里点一句它们的同源关系即可。

2. 每讲要点细化

01 前缀和与差分

主线一句话：前缀和把”区间求和”变成 $O(1)$，差分把”区间修改”变成 $O(1)$，两者互为逆运算。
一维/二维两种形态；什么样的运算能做前缀和（要有逆运算——所以前缀最大值不行）；桶前缀和与多路前缀和。
四个经典模型：最大子段和、和被 $k$ 整除的子段（前缀和 + 同余）、二维前缀和做判定、从差分看操作次数。
它是”预处理换查询”这条主线的起点：ds-series/07 ST 表、ds-series/08 树状数组、ds-series/09~11 线段树做的都是同一笔交易，只是允许”边改边查”。

02 二分查找与二分答案

两套边界模板成套记忆：l<=r + mid±1（找具体值）与 l<r + r=mid（找边界）。死循环的三种成因要给实测错误率。
lower_bound / upper_bound 的语义，以及”为什么 STL 用左闭右开”。
二分答案的三个前提：答案有界、答案单调、给定答案能 $O(n)$ 或 $O(n\log n)$ 验证。识别信号是「最大值最小 / 最小值最大 / 至少要多少」。
check 函数怎么设计——本讲的真正难点。要讲清”判定问题比最优化问题简单一个数量级”这件事。
实数二分与精度：为什么写 for (int i=0;i<100;i++) 比 while (r-l>eps) 稳。
⭐ 三分法：单峰函数求极值，与二分的区别（二分要单调，三分要单峰）。