c++中如何使用std::partial_sum算法_c++计算数组前缀和方法【详解】_技术教程

std::partial_sum是C++标准库计算累积和的算法，默认输出包含自身的前缀和；相比手写循环更简洁、支持自定义操作，但不内置偏移或跳过首项功能，需手动调整迭代器。

std::partial_sum 是什么，它和手写前缀和有什么区别

std::partial_sum 是 C++ 标准库中定义在头文件里的算法，用于就地或输出到另一区间计算**累积和（即前缀和）**。它不区分“严格前缀和”（sum[0..i-1]）还是“包含自身前缀和”（sum[0..i]）——默认行为就是后者：第 i 个输出元素 = 输入区间前 i+1 个元素之和。

和手写循环比，std::partial_sum 更简洁、可读性高、支持自定义二元操作（比如乘积、最大值），且编译器通常能做足够优化；但它不提供“跳过首项”或“偏移起始索引”的内置方式，需手动调整输入/输出迭代器位置来模拟。

基本用法：一维 vector 或数组的前缀和

最常见场景：把 std::vector v = {1,2,3,4}; 变成前缀和 {1,3,6,10}。

输出到新容器（推荐，避免覆盖原数据）：

std::vector v = {1,2,3,4};
std::vector prefix(v.size());
std::partial_sum(v.begin(), v.end(), prefix.begin());

就地计算（原地修改）：

std::partial_sum(v.begin(), v.end(), v.begin()); // v 变为 {1,3,6,10}

注意：std::partial_sum 要求输出迭代器可写，且目标区间长度 ≥ 输入区间长度；否则行为未定义。

用自定义二元操作实现非加法前缀效果

第三个参数可传入任意接受两个同类型参数、返回同类型的函数对象。例如计算前缀积、前缀最小值、字符串拼接前缀等。

前缀积：

std::vector v = {2,3,4};
std::vector prod(v.size());
std::partial_sum(v.begin(), v.end(), prod.begin(), std::multiplies{}); // {2,6,24}

前缀最小值（需注意初始值逻辑）：

std::vector v = {5,3,7,1};
std::vector min_prefix(v.size());
std::partial_sum(v.begin(), v.end(), min_prefix.begin(), [](int a, int b) { return std::min(a, b); }); // {5,3,3,1}

错误写法（混淆了操作顺序）：std::partial_sum(..., std::min{}) 不合法，因为 std::min 是函数模板，不是可调用对象；必须用 lambda 或 std::less{} 等适配形式。

常见坑与边界注意事项

实际编码中容易忽略这些点，导致越界、结果错位或未定义行为：

std::partial_sum 对空区间安全（不执行任何操作），但若输出迭代器为空（如 prefix.begin() 指向空 vector），会写入非法地址 —— 务必保证目标容器已分配足够空间。

不能直接对 C 风格数组做“前缀和偏移”（比如想让 res[i] = v[0]+...+v[i-1]）。必须手动控制迭代器范围，例如：

std::array v{1,2,3,4};
std::array prefix{};
// 实现 res[0]=0, res[1]=v[0], res[2]=v[0]+v[1], ...
prefix[0] = 0;
std::partial_sum(v.begin(), v.end(), prefix.begin()+1); // 注意 +1 偏移