麦地

Back

#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 版
cpp

1. 最大的坑:初始值决定累加类型#

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 累加
cpp

accumulate 的返回类型 = 第三个参数(初始值)的类型,与接收变量无关。求和时一律写 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);        // 0
cpp

与手写欧几里得算法的对比#

// 手写版(必须会写,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) = x
cpp

三、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 15
cpp

等价于:

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];
cpp

partial_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 5
cpp
  • dif[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 那样扩容。


十、一页速记#

四句口诀:

  1. accumulate 写 0LL,初始值类型就是累加类型。
  2. lcm 先除后乘,gcd 会手写也会调库。
  3. iota + sort 是下标排序的标准开场。
  4. partial_sum 和 adjacent_difference 互逆,目标数组先 resize。
Comment seems to stuck. Try to refresh?✨