#include <numeric> // 精确包含
#include <bits/stdc++.h> // 竞赛一把梭cpp掌握优先级总览#
| 函数 | 必考等级 | 一句话用途 |
|---|---|---|
accumulate |
⭐⭐⭐ | 区间累加(和、积、自定义合并) |
gcd / lcm |
⭐⭐⭐ | 最大公约数 / 最小公倍数(C++17) |
iota |
⭐⭐⭐ | 填充连续递增序列(下标数组) |
partial_sum |
⭐⭐⭐ | 前缀和 |
adjacent_difference |
⭐⭐ | 差分(前缀和的逆运算) |
inner_product |
⭐⭐ | 内积 / 加权求和 |
reduce |
⭐ | accumulate 的并行版(C++17) |
midpoint |
⭐⭐ | 防溢出中点(C++20,二分可用) |
一、accumulate:区间累加 ⭐⭐⭐#
vector<int> v = {1, 2, 3, 4, 5};
int sum = accumulate(v.begin(), v.end(), 0); // 15
long long sum2 = accumulate(v.begin(), v.end(), 0LL); // long long 版cpp1. 最大的坑:初始值决定累加类型#
vector<int> v = {1000000000, 1000000000};
long long a = accumulate(v.begin(), v.end(), 0); // 错!int 累加中途溢出
long long b = accumulate(v.begin(), v.end(), 0LL); // 对:long long 累加cppaccumulate 的返回类型 = 第三个参数(初始值)的类型,与接收变量无关。求和时一律写 0LL(整数)或 0.0(浮点)。
2. 第四个参数:自定义二元操作#
// 乘积
int prod = accumulate(v.begin(), v.end(), 1, multiplies<int>());
// 求区间最大值(初始值为最小可能值)
int mx = accumulate(v.begin(), v.end(), INT_MIN,
[](int a, int b) { return max(a, b); });
// 字符串拼接
vector<string> s = {"abc", "de", "f"};
string all = accumulate(s.begin(), s.end(), string("")); // "abcdef"cpp注意:乘积等操作的初始值是单位元(乘法为 1、max 为 INT_MIN),不要习惯性写 0。
3. 复杂度#
O(n),从左到右依次合并。不支持交换律以外的重排(区别于 reduce)。
二、gcd / lcm:数论必考 ⭐⭐⭐(C++17)#
#include <numeric>
gcd(12, 18); // 6
gcd(0, 5); // 5(0 与任何数的 gcd 是该数绝对值)
gcd(0, 0); // 0
gcd(-12, 18); // 6(负数按绝对值处理)
lcm(4, 6); // 12
lcm(0, 5); // 0cpp与手写欧几里得算法的对比#
// 手写版(必须会写,gcd 是理解数论的基础)
int gcd2(int a, int b) {
return b == 0 ? a : gcd2(b, a % b);
}
// 或迭代版
int gcd3(int a, int b) {
while (b) { int t = a % b; a = b; b = t; }
return a;
}cpp竞赛建议:直接用 std::gcd,但手写版必须懂——它是扩展欧几里得、类欧等进阶算法的地基。
lcm 的溢出陷阱#
lcm(a, b); // 实现为 a / gcd(a,b) * b,仍可能溢出 int
// 大数场景手动转 long long:
long long L = (long long)a / gcd(a, b) * b; // 先除后乘,防溢出cpp先除后乘是手写 lcm 的铁律:a * b / gcd(a, b) 会先算 a*b 而溢出。
数组整体的 gcd#
int g = accumulate(v.begin(), v.end(), 0, gcd<int, int>);
// 初始值 0 是 gcd 的单位元:gcd(0, x) = xcpp三、iota:连续递增填充 ⭐⭐⭐#
vector<int> v(10);
iota(v.begin(), v.end(), 1); // 1 2 3 ... 10
vector<int> idx(n);
iota(idx.begin(), idx.end(), 0); // 0 1 2 ... n-1,下标数组cpp竞赛核心用途:下标排序(保留原位置)#
// 按 a 的值排序,但移动的是下标而不是值
vector<int> idx(n);
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&](int i, int j) {
return a[i] < a[j];
});
// idx 就是"排名 → 原下标"的映射cpp这在”输出原数组下标""按值离散处理”的题里极其常用,一行 iota 省掉手写循环。
四、partial_sum:前缀和 ⭐⭐⭐#
vector<int> a = {1, 2, 3, 4, 5};
vector<int> pre(a.size());
partial_sum(a.begin(), a.end(), pre.begin()); // 1 3 6 10 15cpp等价于:
pre[0] = a[0];
for (int i = 1; i < n; i++) pre[i] = pre[i-1] + a[i];cpp竞赛实际用法:区间和查询#
// 常用 1-based 前缀和,手写更直观(两种都要会)
vector<long long> pre(n + 1, 0);
for (int i = 1; i <= n; i++) pre[i] = pre[i-1] + a[i];
// 区间 [l, r] 的和
long long rangeSum = pre[r] - pre[l-1];cpppartial_sum 一行生成前缀和,但竞赛中 1-based 手写版更常见,因为它天然处理 pre[0] = 0 的哨兵。
自定义操作#
// 前缀积
partial_sum(a.begin(), a.end(), pre.begin(), multiplies<int>());
// 前缀最大值
partial_sum(a.begin(), a.end(), pre.begin(),
[](int x, int y) { return max(x, y); });cpp五、adjacent_difference:差分 ⭐⭐#
vector<int> pre = {1, 3, 6, 10, 15};
vector<int> dif(pre.size());
adjacent_difference(pre.begin(), pre.end(), dif.begin()); // 1 2 3 4 5cppdif[0] = pre[0],dif[i] = pre[i] - pre[i-1];- 与
partial_sum互逆:差分后再前缀和还原原数组。
竞赛中差分多用于”区间加法、单点查询”:
// 区间 [l, r] 全部 +x(0-based,dif 长度 n+1)
dif[l] += x;
dif[r+1] -= x;
// 最后做一遍前缀和得到每个位置的最终值
partial_sum(dif.begin(), dif.end(), ans.begin());cpp手写差分数组也很短,库函数版适合”已有前缀和想还原”的场景。
六、inner_product:内积 ⭐⭐#
vector<int> a = {1, 2, 3}, b = {4, 5, 6};
// a·b = 1*4 + 2*5 + 3*6 = 32
int dot = inner_product(a.begin(), a.end(), b.begin(), 0);
// 初始值类型同样决定累加类型
long long dot2 = inner_product(a.begin(), a.end(), b.begin(), 0LL);
// 加权求和、对应位置乘积和都是它cpp可以自定义两种操作(先如何合并每对元素、再如何累加),但竞赛用得少,会默认版即可。
七、reduce:并行累加 ⭐(C++17)#
int sum = reduce(v.begin(), v.end()); // 无初始值,用元素类型默认值
int sum2 = reduce(v.begin(), v.end(), 0); // 带初始值cpp与 accumulate 的区别:
accumulate严格从左到右,有序;reduce允许乱序、分组计算(为并行设计),要求操作满足交换律和结合律(+、*、max 可以,字符串拼接、减法不行)。
不带并行策略时,单线程下两者速度几乎一样,竞赛继续用 accumulate 即可。
八、midpoint:防溢出中点 ⭐⭐(C++20)#
#include <numeric>
int mid = midpoint(lo, hi); // 等价于 lo + (hi - lo) / 2,但保证不溢出cpp二分答案时的经典写法演进:
int mid = (lo + hi) / 2; // 危险:lo + hi 可能溢出 int
int mid = lo + (hi - lo) / 2; // 正确(但 hi < lo 时有符号问题)
int mid = midpoint(lo, hi); // C++20 标准答案,正负都安全cpp评测机支持 C++20 时直接用;否则记住 lo + (hi - lo) / 2。
九、复杂度与陷阱汇总#
| 函数 | 复杂度 | 最大陷阱 |
|---|---|---|
accumulate |
O(n) |
初始值 0 导致 int 溢出 |
gcd / lcm |
O(log min(a,b)) |
lcm 先除后乘防溢出 |
iota |
O(n) |
需要 vector 已有足够 size |
partial_sum |
O(n) |
目标数组需先 resize |
adjacent_difference |
O(n) |
首元素是原样复制 |
inner_product |
O(n) |
初始值类型同样关键 |
通用陷阱:partial_sum、adjacent_difference、inner_product 的输出都写入已有区间,目标容器必须提前分配空间(或用 back_inserter),它们不会像 push_back 那样扩容。
十、一页速记#
#include <numeric>
// 求和:初始值类型 = 累加类型
accumulate(v.begin(), v.end(), 0LL);
// 自定义合并(乘积 / max / 拼接)
accumulate(v.begin(), v.end(), 1, multiplies<int>());
accumulate(s.begin(), s.end(), string(""));
// 数论
gcd(a, b); lcm(a, b);
long long L = (long long)a / gcd(a, b) * b; // 先除后乘
// 数组 gcd
accumulate(v.begin(), v.end(), 0, gcd<int,int>);
// 下标数组 + 下标排序
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&](int i, int j){ return a[i] < a[j]; });
// 前缀和 / 差分(互逆)
partial_sum(a.begin(), a.end(), pre.begin());
adjacent_difference(pre.begin(), pre.end(), dif.begin());
// 内积
inner_product(a.begin(), a.end(), b.begin(), 0LL);
// 防溢出中点(C++20)
midpoint(lo, hi);cpp四句口诀:
accumulate写0LL,初始值类型就是累加类型。lcm先除后乘,gcd会手写也会调库。iota + sort是下标排序的标准开场。partial_sum和adjacent_difference互逆,目标数组先resize。