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 要求输出迭代器可写，且目标区间长度 ≥ 输入区间长度；否则行为未定义。

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

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

LangChain

一个开源框架，用于构建基于大型语言模型（LLM）的应用程序。

下载

立即学习“C++免费学习笔记（深入）”；

• 前缀积：

  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 偏移

• 输入和输出区间重叠时（如就地计算），必须确保输出不会覆盖尚未读取的输入值 —— std::partial_sum 内部按从左到右顺序计算，所以 v.begin() → v.begin() 是安全的，但 v.begin()+1 → v.begin() 就不行。

真正要注意的是：它永远从第一个元素开始累加，没有“排除首项”或“指定起始索引”的参数；需要这类语义时，得靠调整迭代器或预置初值来模拟。