常用算法代码模板（C++）——基础算法：排序、二分、高精度、前缀和与差分、位运算、双指针、离散化、区间合并
C++算法模板系列
目录
1 排序
std::sort(begin, end, cmp)
1.1 直接插入排序
int n;
int q[N]; // q[0 ... n-1]
void insert_sort() {
for (int i = 1; i < n; i++) {
for (int j = i; j >= 1 && q[j] > q[j - 1]; j--) {
swap(q[j], q[j - 1]);
}
}
}
1.2 快速排序
- 确定枢轴：通常从
q[l]、q[l + r >> 1]、q[r]之中任选一个 - 划分子区间：双指针
i、j初始位于待排区间两侧外，先i后j相向而行，最终使得左右子区间q[l ... j]、q[j+1 ... r]左小右大 - 递归排序左右子区间（该写法左子区间右端点必须为
j）
int q[N]; // q[l ... r]
void quick_sort(int l, int r) {
if (l >= r) return; // 只剩一个数或没有数了则不排序
int x = q[l + r >> 1]; // 枢轴（可选 q[l]、q[l + r >> 1]、q[r]）
int i = l - 1, j = r + 1; // 双指针初始位于两侧外（追加1偏移量）
while (i < j) { // 进行一轮划分操作
do i++; while (q[i] < x);
do j--; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(l, j); // 左子区间右端点必须为j
quick_sort(j + 1, r);
}
1.3 归并排序
- 确定分界点：
mid = l + r >> 1 - 递归排序左右子区间
- 归并左右子区间为有序子区间：挑出两者较小值，相等则优先归并
q[i]，使得排序稳定
int q[N]; // q[l ... r]
int tmp[N]; // 辅助数组tmp临时存放新区间
void merge_sort(int l, int r) {
if (l >= r) return; // 只剩一个数或没有数了则不排序
int mid = l + r >> 1; // 确认分界点：左[l, mid]、右[mid + 1, r]
merge_sort(l, mid);
merge_sort(mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r) // 归并左右子区间为有序子区间：挑出两者较小值
if (q[i] <= q[j]) {
tmp[k++] = q[i++]; // 相等则优先归并q[i]，否则排序不稳定
} else {
tmp[k++] = q[j++];
}
while (i <= mid) {
tmp[k++] = q[i++];
}
while (j <= r) {
tmp[k++] = q[j++];
}
for (i = l, j = 0; i <= r; ++i, ++j) {
q[i] = tmp[j]; // 将tmp[0 ... r-l+1]复制给q[l ... r]
}
}
2 二分
整数二分：AcWing 789. 数的范围
- 中点将区间划分出左右两子区间
- 判断中间点是否满足某侧区间的性质
check(mid)，查找x边界，目标在x区间，检测x区间性质。易知该种写法条件检测始终为"≥"或"≤"，对应下文记号check_ge()（greater_equal）、check_le()（less_equal），对比目标和中点的位置关系即可得出条件检测函数。 - 返回所检测的x区间的端点x
当查找右边界时中点应为
l + r + 1 >> 1，简记：有("右") 加必有("右") 减
浮点数二分：类似整数二分的查找左边界，常写作f(mid) >= target的形式。解唯一，无需处理边界。要注意浮点精度问题。
/* 查找左边界，即第一个满足条件的元素下标 (lower_bound) */
int bsearch_l(int l, int r) {
while (l < r) {
int mid = l + r >> 1;
if (check_ge(mid, target)) {
r = mid; // 目标在左，mid所指>=目标：带mid去左边[l, mid]
} else {
l = mid + 1; // 否则去右边 [mid + 1, r]
}
}
return l;
}
/* 查找右边界，即最后一个满足条件的元素下标 (upper_bound的前驱) */
int bsearch_r(int l, int r) {
while (l < r) {
int mid = l + r + 1 >> 1; // 有(“右”)加必有(“右”)减
if (check_le(mid, target)) {
l = mid; // 目标在右，mid所指<=目标：带mid去右边[mid, r]
} else {
r = mid - 1; // 否则去左边: [l, mid - 1]
}
}
return r;
}
/* 浮点数二分 */
int bsearch_f(double l, double r) {
const double eps = 1e-8; // 精度，视题目而定
while (r - l > eps) {
double mid = (l + r) / 2;
if (check_ge(mid, target)) {
r = mid; // 目标在左，mid所指>=目标。注意浮点关系运算精度问题
} else {
l = mid; // 边界均无需+1或-1
}
}
return l;
}
3 C++高精度运算
C++使用变长数组vector
3.1 高精度加法
/* C = A + B, A >= 0, B >= 0 */
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(t); // 存入最后的进位
}
return C;
}3.2 高精度减法
/* 比较两个高精度整数的大小，返回A - B的符号 */
int cmp(vector<int> &A, vector<int> &B) {
if (A.size() > B.size()) return 1; // 优先比较长度
else if (A.size() < B.size()) return -1;
for (int i = A.size() - 1; i >= 0; i--) // 从高位起逐位比较
if (A[i] > B[i]) return 1;
else if (A[i] < B[i]) return -1;
return 0;
}
/* C = A - B, A >= B, A >= 0, B >= 0 */
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]; // 先直接相减，t<0则说明需借位
C.push_back((t + 10) % 10); // 若t<0，则存的是借位后的差；否则正常存差
if (t < 0) { // 判断是否需借位
t = 1;
} else {
t = 0;
}
}
while (C.size() > 1 && C.back() == 0) {
C.pop_back(); // 去除前导0（结果为0则保留1位）
}
return C;
}3.3 高精度乘低精度
/* C = A * b, A >= 0, b >= 0 */
vector<int> mul(vector<int> &A, int b) {
vector<int> C;
int t = 0; // 进位
for (int i = 0; i < A.size() || t; i++) { // 自动处理最后剩余进位(i>=size但t>0)
if (i < A.size()) t += A[i] * b;
C.push_back(t % 10);
t /= 10;
}
// if (t) C.push_back(t);
while (C.size() > 1 && C.back() == 0) {
C.pop_back(); // b为0时，需去除前导0
}
return C;
}3.4 高精度除以低精度
/* A / b = C ... r, A >= 0, b > 0 */
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;
}4 前缀和、差分
以下前缀和与差分数组必须从下标1开始存储
4.1 一维前缀和
对于数列a[1], a[2], ... , a[n]，规定a[i]的前缀和为前$i$个数的和：s[i] = a[1] + a[2] + ... + a[i] (i >= 1)
求法：s[0] = 0, s[i] = s[i - 1] + a[i] (i >= 1)
应用：求下标区间$[l,\ r]$上的片段和s[r] - s[l - 1]
int n;
int a[N], s[N]; // [1 ... n]
/* 初始化前缀和数组 */
for (int i = 1; i <= n; i++) {
s[i] = s[i - 1] + a[i];
}
/* 求下标区间[l, r]上的片段和 */
int sum = s[r] - s[l - 1]; // sum = a[l] + ... + a[r]4.2 二维前缀和
对于n * m的矩阵a[n][m]，规定a[i][j]的二维前缀和s[i][j]为元素a[i][j]左上角所有元素的和。
求法：s[0][j] = s[i][0] = s[0][0] = 0, s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j] (i, j >= 1)
应用：求下图以(x1, y1)为左上角、(x2, y2)为右下角的子矩阵（含边界）上的片段和，只需将整块左上矩形面积减去红、绿区域（不含待求区域边界）面积再补上多减去的重叠区域面积，即为S = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]
int n, m;
int a[N][N], s[N][N]; // [1 ... n][1 ... m]
/* 初始化前缀和数组 */
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
}
}
/* 求以(x1, y1)为左上角、(x2, y2)为右下角的子矩阵（含边界）上的片段和 */
int sum = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];4.3 一维差分
由数组a[1], a[2], ... ,a[n]构造差分数组b[1], b[2], ... , b[n]，使得a[i] = b[1] + b[2] + ... + b[i]，b[i] = a[i] - a[i - 1]
应用：给区间[l, r]上所有数加上C，时间复杂度 $O(1)$。方法如下
- 给
b[l]加上C，使得a[l], a[l + 1], ... , a[n]均加上了C - 给
b[r + 1]减去C，使得a[r + 1], a[r + 2], ... , a[n]均减去了本不应加的C
对于原差分数组的初始化亦可采用上述操作，赋值
a[i]即相当于给区间[i, i]加上a[i]
int n;
int a[N], b[N]; // [1 ... n]
/* 给区间[l, r]上所有数加上c */
void insert(int l, int r, int c) {
b[l] += c;
b[r + 1] -= c;
}
/* 初始化差分数组 */
for (int i = 1; i <= n; i++) {
insert(i, i, a[i]);
}
/* 将操作过的差分数组变为原数组（前缀和与差分互为逆运算） */
for (int i = 1; i <= n; i++) {
b[i] += b[i - 1];
}4.4 二维差分
参考一维差分与二维前缀和，差分矩阵中每个数都蕴含于其右下矩阵中的每个数。
操作：给下图以(x1, y1)为左上角、(x2, y2)为右下角的子矩形（含边界）加上C，只需给整个右下角加C，给红、绿区域各减C，最后再给重叠区域加上多减的C即可
对于原差分矩阵初始化操作亦可采用上述操作，参考一维差分
int n, m;
int a[N][N], b[N][N]; // [1 ... n][1 ... m]
/* 给以(x1, y1)为左上角、(x2, y2)为右下角的子矩阵（含边界）加上c */
void insert(int x1, int y1, int x2, int y2, int c) {
b[x1][y1] += c;
b[x2 + 1][y1] -= c;
b[x1][y2 + 1] -= c;
b[x2 + 1][y2 + 1] += c;
}
/* 初始化差分矩阵 */
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
insert(i, j, i, j, a[i][j]);
}
}
/* 将操作过的差分矩阵变为原矩阵：求差分矩阵的前缀和 */
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
}
}5 位运算
- 求 $n$ 的二进制表示中第 $k$ 位数字：
n >> k & 1（先把第 $k$ 位数字移到最后一位，再看个位是几，即和 $1$ 做按位与运算） lowbit(n)：返回 $n$ 的最后一位 $1$
int lowbit(int x) {
return x & -x; // -n = ~n + 1
}
/* 应用 */
// 输出整数x的二进制表示（31位）
for (int i = 0; i < 31; i++) {
printf("%d", x >> i & 1);
}
// 统计x的二进制表示中有几位1
int cnt = 0;
while (x) {
x -= lowbit(x);
cnt++;
}6 双指针算法
常见的双指针问题：
- 对于一个序列，用两个指针维护一段区间
- 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作
/* 朴素算法 O(n^2) */
// for (int i = 0; i < n; i++) {
// for (int j = i; j < n; j++) {
// ...
// }
// }
/* 双指针优化后的算法 O(n) */
/* 例1 */
for (int i = 0, j = 0; i < n; i++) { // i为子序列右端点，j为左端动点
while (j < i && check(i, j)) {
...
j++;
}
...
}
/* 例2 */
for (int i = 0; i < n;) { // i为子序列左端点，j为动态右端动点
int j = i;
while (j < n && check(i, j)) {
...
j++;
}
...
i = j + 1; // 将i直接移至j附近
}7 离散化
高度分散的整数 → $0, 1, 2, ..., n-1$ 或 $1, 2, ..., n$
vector<int> alls; // 存储所有待离散化的值
/* 离散化（保序） */
sort(alls.begin(), all.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), all.end()); // 去重
/* 根据离散化的值k获取原来的值x */
int x = alls[k];
/* 二分求出x对应的离散化的值 */
int find(int x) {
int l = 0, r = alls.size() - 1;
while (l < r) { // 找到第1个大于等于x的位置（唯一）
int mid = l + r >> 1;
if (alls[mid] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return r + 1; // 这里+1是为了映射到1, 2, ..., alls.size()
}8 区间合并
- 先将所有区间按左端点大小排序
- 当前维护区间与下一区间之间分三种情况：包含、有交集（含端点）、无交集
- 包含：无需操作（实为有交集的特殊情况）
- 有交集：更新当前区间右端点为较大的即可，继续维护
- 无交集：结束维护当前区间并保存，更新为下一区间
- 迭代结束后保存当前维护区间
typedef pair<int, int> PII; // <st, ed>
/* 合并区间 */
vector<PII> merge(vector<PII> &segs) {
vector<PII> res;
sort(seg.begin(), seg.end()); // 默认优先按first（左端点大小）排序
int st = -INF, ed = -INF; // 当前维护区间（初始化为负无穷）
for (auto &seg : segs) {
if (ed < seg.first) { // 若与当前维护区间无交集
if (st != -INF) {
res.push_back({st, ed}); // 当前区间结束维护并保存
}
st = seg.first; // 转移至此区间
ed = seg.second;
} else {
ed = max(ed, seg.second); // 有交集则比较右端点即可，继续维护
}
}
if (st != -INF) {
res.push_back({st, ed}); // 保存最后一个区间
}
return res;
}