算法笔记:AcWing - 基础算法

算法笔记:AcWing - 基础算法

Ginkgo True love prevails.

写这篇的初衷:很多算法模板背了就忘,核心是没理解为什么要这样写。这篇试着从”什么时候用”和”为什么有效”两个角度重新整理。

更进一步的初衷:最近要开始找实习了,好久没碰算法,已经比较生疏了,算是一次 “温故而知新”


一、排序:快排 vs 归并

快速排序 —— “分而治之”的典型

什么时候用:日常排序首选,平均性能最好,原地排序不占额外空间。

核心直觉:随便选个数当”标杆”(pivot),把比它小的扔左边,比它大的扔右边,然后对左右两边递归干同样的事。

为什么快:每次划分后,pivot 就回到了它最终应该在的位置。理想情况下每次划分都是中点,递归深度是 ,每层扫描一遍数组,总复杂度 。

但要注意:最坏情况(数组已经有序)会退化成 。解决方法是随机选 pivot 或者三数取中。

1
2
3
4
5
6
7
8
9
10
11
void quick_sort(vector<int>& arr, int l, int r) {
if (l >= r) return;
int pivot = arr[l], i = l - 1, j = r + 1;
while (i < j) {
while (arr[++i] < pivot); // 左边找>=pivot 的
while (arr[--j] > pivot); // 右边找<=pivot 的
if (i < j) swap(arr[i], arr[j]);
}
quick_sort(arr, l, j);
quick_sort(arr, j + 1, r);
}

易错点:选 arr[l] 做 pivot 时,递归要写 quick_sort(arr, l, j) 而不是 l, mid,因为划分后 j 才是分界点。


归并排序 —— 稳定且可预测

什么时候用:

  • 需要稳定排序(相同元素的相对顺序不变)
  • 链表排序(不需要额外空间)
  • 求逆序对(归并过程中可以顺便统计)

核心直觉:先把数组拆到最小(单个元素天然有序),然后两两合并。合并时两个指针分别指向两个有序段,每次取较小的那个。

为什么稳定:合并时遇到相等的元素,优先取左边段的,所以相对顺序不会变。

代价:需要 额外空间存临时数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void merge_sort(vector<int>& arr, int l, int r) {
if (l >= r) return;
int mid = l + r >> 1;
merge_sort(arr, l, mid);
merge_sort(arr, mid + 1, r);

// 合并两个有序段 [l, mid] 和 [mid+1, r]
int k = 0, i = l, j = mid + 1;
vector<int> tmp(r - l + 1);
while (i <= mid && j <= r)
if (arr[i] <= arr[j]) tmp[k++] = arr[i++];
else tmp[k++] = arr[j++];
while (i <= mid) tmp[k++] = arr[i++];
while (j <= r) tmp[k++] = arr[j++];

for (i = l, j = 0; i <= r; ++i, ++j)
arr[i] = tmp[j];
}

二、二分查找:不只是”有序数组找数”

核心思想

二分的本质不是”找数”,而是根据某种单调性,每次排除一半的搜索空间。

关键:找到那个可以判断”答案在左边还是右边”的性质。


整数二分:两个模板

场景 1:找满足性质的最小值(比如找第一个>=x 的位置)

区间划分:[l, mid] 和 [mid+1, r]

1
2
3
4
5
6
7
8
int bsearch_1(vector<int>& arr, int l, int r, int x) {
while (l < r) {
int mid = l + r >> 1;
if (arr[mid] >= x) r = mid; // mid 可能是答案,保留
else l = mid + 1; // mid 肯定不是,排除
}
return l;
}

场景 2:找满足性质的最大值(比如找最后一个<=x 的位置)

区间划分:[l, mid-1] 和 [mid, r]

1
2
3
4
5
6
7
8
int bsearch_2(vector<int>& arr, int l, int r, int x) {
while (l < r) {
int mid = l + r + 1 >> 1; // 注意这里要 +1
if (arr[mid] <= x) l = mid; // mid 可能是答案,保留
else r = mid - 1; // mid 肯定不是,排除
}
return l;
}

为什么要 +1:整数除法向下取整。当 l = r-1 时,不加 1 则 mid = l,如果 check 为真,l = mid 还是等于 l,死循环。加 1 后 mid = r,可以正常推进。


浮点数二分:更简单

不用考虑边界问题,直接缩小区间直到足够小:

1
2
3
4
5
6
double l = 0, r = 1e9;
for (int i = 0; i < 100; i++) { // 循环 100 次精度足够
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}

三、高精度运算:当数字超出 long long

什么时候用:数字超过 18 位(long long 上限),比如 这种。

核心思想:用数组存每一位,模拟小学竖式计算。

存储技巧:倒序存储,arr[0] 存个位,方便进位时直接 push_back。


高精度加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> add(vector<int>& A, vector<int>& B) {
if (A.size() < B.size()) return add(B, A);

vector<int> C;
int t = 0; // 进位
for (int i = 0; i < A.size(); i++) {
t += A[i];
if (i < B.size()) t += B[i];
C.push_back(t % 10);
t /= 10;
}
if (t) C.push_back(1); // 最后还有进位
return C;
}

高精度减法

前提:保证 A >= B,如果不确定要先比较大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> sub(vector<int>& A, vector<int>& B) {
vector<int> C;
int t = 0; // 借位
for (int i = 0; i < A.size(); i++) {
t = A[i] - t;
if (i < B.size()) t -= B[i];
C.push_back((t + 10) % 10); // 处理负数
t = (t < 0) ? 1 : 0;
}
// 去掉前导 0
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}

高精度乘法(大数×小数)

1
2
3
4
5
6
7
8
9
10
vector<int> mul(vector<int>& A, int b) {
vector<int> C;
int t = 0;
for (int i = 0; i < A.size() || t; i++) {
if (i < A.size()) t += A[i] * b;
C.push_back(t % 10);
t /= 10;
}
return C;
}

高精度除法(大数÷小数)

注意:除法要正序处理,从高位开始。

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> div(vector<int>& A, int b, int& r) {
vector<int> C;
r = 0;
for (int i = A.size() - 1; i >= 0; i--) {
r = r * 10 + A[i];
C.push_back(r / b);
r %= b;
}
reverse(C.begin(), C.end()); // 结果要倒过来
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}

四、前缀和与差分:区间查询/修改的神器

前缀和 —— 快速求区间和

场景:频繁查询某个区间的和,但数组本身不修改。

原理:预处理出 S[i] = a[1] + ... + a[i],那么区间 [l, r] 的和就是 S[r] - S[l-1]。

为什么快:预处理 ,每次查询 。

1
2
3
4
5
6
7
// 一维前缀和
vector<int> pre(n + 1);
for (int i = 1; i <= n; ++i)
pre[i] = pre[i - 1] + a[i];

// 查询 [l, r] 的和
int sum = pre[r] - pre[l - 1];

二维前缀和 —— 子矩阵求和

场景:求矩阵中某个子矩形的元素和。

公式:

直觉:大矩形减去左边和上边,但左上角被减了两次,要加回来。

1
2
3
4
5
6
7
// 预处理
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j];

// 查询 (x1,y1) 到 (x2,y2) 的子矩阵
int sum = pre[x2][y2] - pre[x2][y1-1] - pre[x1-1][y2] + pre[x1-1][y1-1];

差分 —— 快速区间修改

场景:频繁对某个区间统一加/减一个数,最后再查询。

原理:差分和原数组的关系是”前缀和的逆运算”。对原数组区间 [l, r] 加 c,等价于差分数组 b[l] += c,b[r+1] -= c。

为什么快:修改 ,最后还原一遍前缀和即可。

1
2
3
4
5
6
7
8
9
10
11
12
// 差分数组
vector<int> b(n + 2);

// 区间 [l, r] 加 c
b[l] += c;
b[r + 1] -= c;

// 最后还原
for (int i = 1; i <= n; ++i) {
b[i] += b[i - 1];
// b[i] 就是原数组 a[i] 的值
}

二维差分 —— 子矩阵批量修改

1
2
3
4
5
6
7
8
9
10
// 对子矩阵 (x1,y1) 到 (x2,y2) 加 c
d[x1][y1] += c;
d[x1][y2 + 1] -= c;
d[x2 + 1][y1] -= c;
d[x2 + 1][y2 + 1] += c;

// 还原
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
d[i][j] += d[i-1][j] + d[i][j-1] - d[i-1][j-1];

五、双指针法:从 到

核心思想:利用单调性,用两个指针维护一个区间,避免嵌套循环。

典型场景:

  • 找最长/最短满足某条件的子数组
  • 两数之和
  • 滑动窗口问题

模板:

1
2
3
4
5
6
for (int i = 0, j = 0; i < n; i++) {
// i 向右移动,j 跟着调整以保持区间性质
while (j < n && check(i, j))
j++;
// [i, j) 就是满足条件的区间
}

例子:找最长不重复子串

1
2
3
4
for (int i = 0, j = 0; i < n; i++) {
while (j < n && !hasDuplicate(i, j)) j++;
ans = max(ans, j - i);
}

六、位运算:一些实用技巧

取第 k 位

1
int bit = (n >> k) & 1;  // 右移 k 位后和 1 做与运算

Lowbit —— 提取最低位的 1

1
2
3
int lowbit(int n) {
return n & (-n);
}

原理:-n 的补码是 ~n + 1,与 n 相与后只有最低位的 1 保留。

应用:树状数组的核心操作。


七、离散化:值域太大怎么办

场景:数字范围很大(比如 ),但实际出现的数字很少(比如只有 个)。

思路:把出现过的数字排序去重,然后用它们的排名代替原值。

1
2
3
4
5
6
7
8
vector<int> all;  // 收集所有需要离散化的值
// ... 把原数组和查询的值都加进去

sort(all.begin(), all.end());
all.erase(unique(all.begin(), all.end()), all.end());

// 对任意值 x,找它的离散化后的值(排名)
int idx = lower_bound(all.begin(), all.end(), x) - all.begin() + 1;

好处:原本需要开 的数组,现在只需要开 。


八、区间合并:把有交集的区间合并

场景:给定一堆区间,合并所有有交集的。

思路:

  1. 按左端点排序
  2. 遍历,如果当前区间和上一个有交集就合并,否则新开一个
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void merge(vector<pair<int, int>>& segs) {
vector<pair<int, int>> res;
sort(segs.begin(), segs.end());

int st = -2e9, ed = -2e9;
for (auto seg : segs) {
if (ed < seg.first) { // 无交集
if (st != -2e9) res.push_back({st, ed});
st = seg.first;
ed = seg.second;
} else { // 有交集,扩展右端点
ed = max(ed, seg.second);
}
}
if (st != -2e9) res.push_back({st, ed});

segs = res;
}

小结

这些基础算法的核心不是背模板,而是理解:

算法 核心思想 典型场景
快排 分治 + 分区 日常排序
归并 分治 + 合并 稳定排序、逆序对
二分 单调性排除 找边界、答案二分
前缀和 预处理换查询 区间求和
差分 延迟修改 区间加减
双指针 单调性优化 滑动窗口
离散化 值域压缩 大值域小数量

下一篇整理数据结构部分~

  • Title: 算法笔记:AcWing - 基础算法
  • Author: Ginkgo
  • Created at : 2026-04-05 18:56:34
  • Updated at : 2026-04-12 16:22:23
  • Link: https://g1nkgo7.github.io/2026/04/05/算法笔记-AcWing-基础算法/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments