网硕互联帮助中心摘要：还在为算法基础不牢而苦恼？面对题目不知道用什么算法？本文将 algorithm 竞赛中最核心的基础算法一网打尽！从最常用的二分、尺取，到数据处理神器前缀和、差分、离散化，再到进阶的倍增、ST表，最后深入探讨贪心算法背后的数学原理——拟阵。无论你是蓝桥杯、考研机试还是 ACMer，这篇文章都是你的兵器库。建议收藏反复研读！
目录
- 尺取法（双指针）：像虫子一样蠕动
- 二分法：不仅是查找，更是答案的判定
- 三分法：凸函数的极值克星
- 前缀和与差分：区间操作的
O
(
1
)
O(1)
O(1) 秘密 - 离散化：让
10
9
10^9
109 的数据乖乖排队 - 排列与排序：STL 的骚操作
- 分治法：大事化小，各个击破
- 倍增法与 ST 表：预处理的
2
k
2^k
2k 智慧
- 贪心法：局部最优能否推出全局最优？
- 拟阵（Matroid）：贪心算法的理论基石（硬核！）
第一部分：搜索与遍历的艺术
1. 尺取法（双指针 / Two Pointers）
核心思想：利用区间的单调性，通过两个指针（
L
,
R
L, R
L,R）像毛毛虫一样在数组上蠕动，避免
O
(
N
2
)
O(N^2)
O(N2) 的暴力枚举。
模版代码：
// 寻找满足条件的最短区间长度
void solve(int n, int S, vector<int>& a) {
int l = 0, r = 0, sum = 0, res = n + 1;
while (true) {
while (r < n && sum < S) { // 1. 右指针不断进食
sum += a[r++];
}
if (sum < S) break; // 无法满足，结束
res = min(res, r – l); // 更新答案
sum -= a[l++]; // 2. 左指针收缩
}
}
相应例题：P1638 逛画展
2. 二分法（Binary Search）
痛点：很多人写二分死循环。 秘籍：认准一个模版（while(l < r)），不要混用。
整数二分模版（查找左边界）：
// 检查 x 是否满足某种性质
bool check(int x) { /* … */ }
int bsearch_1(int l, int r) {
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) r = mid; // 答案在左边，包含 mid
else l = mid + 1; // 答案在右边
}
return l;
}
进阶：二分不仅查下标，更多时候用于二分答案（例如：最大化最小值）。
3. 三分法（Ternary Search）
场景：二分解决单调函数，三分解决凸函数/凹函数（求极值）。 原理：取两个点
m
1
,
m
2
m1, m2
m1,m2 将区间三等分，比较函数值舍去一段。
double l = 0, r = 1000;
while (r – l > 1e-7) {
double m1 = l + (r – l) / 3;
double m2 = r – (r – l) / 3;
if (f(m1) < f(m2)) l = m1; // 求最大值时，m1 肯定不是峰值
else r = m2;
}
第二部分：数据的魔法处理
1. 前缀和与差分
这是一对互逆运算，专门处理区间问题。
- 前缀和：快速求区间和
O
(
1
)
O(1)
O(1)。- 公式：sum[i] = sum[i-1] + a[i]
- 查询 [L, R]：sum[R] – sum[L-1]
- 差分：快速进行区间修改
O
(
1
)
O(1)
O(1)。- 操作：给区间 [L, R] 全部加上 k。
- 核心：diff[L] += k; diff[R+1] -= k;
- 最后做一次前缀和还原原数组。
2. 离散化（Discretization）
场景：数值很大（如
10
9
10^9
109），但数据个数很少（如
10
5
10^5
105），且我们只关心他们的大小关系，不关心具体数值。
STL 三步走模版：
vector<int> a; // 存原始数据
vector<int> b = a; // 备份
sort(b.begin(), b.end()); // 1. 排序
b.erase(unique(b.begin(), b.end()), b.end()); // 2. 去重
// 3. 查找 x 离散化后的值（排名）
int get_id(int x) {
return lower_bound(b.begin(), b.end(), x) – b.begin() + 1;
}
3. 排序与排列
除了 sort，C++ STL 还有一个神器：next_permutation（生成下一个字典序排列）。 全排列模版：
vector<int> p = {1, 2, 3};
do {
// 处理当前排列
} while (next_permutation(p.begin(), p.end()));
有感兴趣的可以参考我之前的一篇文章算法随笔：洛谷P1036 选数
第三部分：分治与倍增
1. 分治法（Divide and Conquer）
口诀：分而治之，合二为一。 经典案例：归并排序求逆序对、快速幂。
- 快速幂：
a
b
a^b
ab 可以在O
(
log
b
)
O(\\log b)
O(logb) 内算出。long long qpow(long long a, long long b) {
long long res = 1;
while (b) {
if (b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
2. 倍增法与 ST 表
倍增思想：任何数字都可以表示为
2
2
2 的幂次之和。 ST 表（Sparse Table）：解决 RMQ（区间最值查询） 问题，不支持修改，但查询是
O
(
1
)
O(1)
O(1) 的！
核心转移方程：
f
[
i
]
[
j
]
=
max
(
f
[
i
]
[
j
−
1
]
,
f
[
i
+
(
1
<
<
(
j
−
1
)
)
]
[
j
−
1
]
)
f[i][j] = \\max(f[i][j-1], f[i + (1 << (j-1))][j-1])
f[i][j]=max(f[i][j−1],f[i+(1<<(j−1))][j−1]) 意思是：以
i
i
i 开始长度为
2
j
2^j
2j 的最大值，等于左半边的最大值和右半边的最大值取 max。 相应例题：P3865 【模板】ST 表 & RMQ 问题
第四部分：贪心的数学之美
1. 贪心法（Greedy）
定义：顾名思义就是在每一步选择中都采取当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。 难点：证明。很多时候直觉是错的，需要通过“交换论证法”或“反证法”来证明。
2. 拟阵（Matroid）：贪心的理论基石
你是否疑惑过：为什么最小生成树（Kruskal）可以用贪心？为什么硬币找零问题在某些面额下贪心会失效？ 这一切的背后，都有一个数学结构在支撑——拟阵。
什么是拟阵？ 简单来说，拟阵
M
=
(
S
,
I
)
M = (S, I)
M=(S,I) 是一个二元组，其中
S
S
S 是有限集合，
I
I
I 是
S
S
S 的子集族（称为独立集），满足以下三个公理：
I
I
I。
A
A
A 和
B
B
B，且
∣
A
∣
<
∣
B
∣
|A| < |B|
∣A∣<∣B∣，那么一定存在一个元素
x
∈
B
−
A
x \\in B-A
x∈B−A，使得
A
∪
{
x
}
A \\cup \\{x\\}
A∪{x} 也是独立的。
结论：
如果一个最优化问题可以被建模为“在拟阵中寻找权值最大的独立集”，那么贪心算法一定能得到全局最优解。
例子：
- 图的生成树就是一个拟阵（图形拟阵）。所以 Kruskal 算法（贪心）是正确的。
- 线性基也是一个拟阵（向量拟阵）。
第五部分：总结
基础算法是地基，地基不牢，地动山摇。
- 遇到
10
9
10^9
109 数据？先想离散化。 - 求区间最值？静态用 ST表，动态用线段树（进阶）。
- 判定答案容易，求答案难？二分答案。
- 贪心拿不准？试着往拟阵的交换性上想一想。
希望这篇总结能成为你刷题路上的灯塔！
评论区打卡：你觉得最难理解的基础算法是哪个？
评论前必须登录！
注册