C++ partial_sum深度解析：从前缀和到序列变换的进阶应用

1. 从求和到变换：重新认识partial_sum

如果你写过C++，对std::accumulate这个算法一定不陌生，它用来计算一个区间内所有元素的总和，是“求和”操作的代名词。但今天要聊的std::partial_sum，虽然名字里也带着“sum”，它的能力却远不止于此。很多开发者对它停留在“计算前缀和”的浅层认知，觉得这不过是个accumulate的“渐进版”，但实际上，它是一个被严重低估的“序列变换器”。

简单来说，std::partial_sum会遍历一个输入区间，将当前元素与之前所有元素的“累积结果”进行二元运算，并将每次运算的结果输出到另一个区间。默认的二元运算是加法，所以它天然地用来计算前缀和：给定序列[a, b, c, d]，输出就是[a, a+b, a+b+c, a+b+c+d]。这个特性在算法竞赛、数据处理、信号分析等领域非常有用，比如快速计算子数组和、进行积分近似等。

但它的精髓在于第二个参数：一个可自定义的二元函数。一旦你意识到，这个“累积”操作可以是任何满足结合律的运算，partial_sum的视野就瞬间打开了。乘法、最大值、最小值、字符串连接，甚至是自定义的复杂状态合并逻辑，都可以通过它来优雅地实现。它本质上是一个“扫描”（Scan）操作，是函数式编程中fold（折叠）的“过程可视化”版本。理解这一点，是你从“会用”到“精通”这个函数的关键。

在接下来的内容里，我不会只给你罗列API签名和简单例子。我们会深入它的实现机理，探讨它在不同场景下的应用模式，分析其性能特性和可能遇到的坑，并分享一些我实践中总结出来的、能让代码更清晰、更高效的使用技巧。无论你是正在刷题准备面试，还是在开发需要处理序列数据的实际项目，相信这些内容都能给你带来新的启发。

2. 核心机理：不止于加法的“扫描”操作

要真正用好std::partial_sum，不能只把它当黑盒，理解其内部的工作流程和设计意图至关重要。这能帮助你在复杂场景下做出正确判断，避免误用。

2.1 函数签名与行为定义

我们首先看下它在<numeric>头文件中的两个重载形式：

template< class InputIt, class OutputIt > OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first ); template< class InputIt, class OutputIt, class BinaryOperation > OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first, BinaryOperation op );

参数很清晰：first和last定义输入区间，d_first是输出区间的起始位置。关键在第二个版本的自定义操作op。

它的行为可以用如下伪代码精确描述：

1. 如果输入区间非空，直接将*first赋值给*d_first。
2. 然后，对于后续的每个输入元素*(first + i)(i >= 1)，执行：*(d_first + i) = op(*(d_first + i - 1), *(first + i))注意！这里进行运算的第一个参数是前一个输出结果，第二个参数是当前输入元素。这个顺序非常重要，它决定了运算的“方向”是左结合的。

让我们用一个具体的例子，抛开加法，用乘法来感受这个过程：

std::vector<int> input = {1, 2, 3, 4}; std::vector<int> output(4); // 使用乘法作为op std::partial_sum(input.begin(), input.end(), output.begin(), std::multiplies<int>()); // output 的结果是 [1, 1*2, 2*3, 6*4] 即 [1, 2, 6, 24]

这个过程清晰地展示了“累积”的概念：每一步的运算都依赖于上一步的结果。这不仅仅是数学计算，任何有状态的、需要基于前序结果和当前输入产生新输出的过程，都可以套用这个模型。

2.2 与相邻差分的逆运算关系

std::partial_sum有一个天生的“搭档”——std::adjacent_difference。后者计算序列中相邻元素的差（或自定义运算结果）。它们之间存在着有趣的逆运算关系。

对于一个序列S，先做差分再做前缀和，理论上应该能还原原序列（边界可能有细微差别）。但这里有一个极其重要的细节：std::adjacent_difference的默认操作是计算*i - *(i-1)，而std::partial_sum的默认操作是加法。它们是互逆的。

更一般化地，如果你为partial_sum定义了自定义操作op，那么为了使其可逆，你需要为adjacent_difference定义相应的逆操作inv_op，使得inv_op(op(a, b), a) == b成立。例如，如果op是乘法，那么inv_op就应该是除法。这个特性在数据压缩、编码解码或需要保存差分数据以节省空间的场景下非常有用。

注意：partial_sum和adjacent_difference的逆关系在数学上是完美的，但在浮点数计算中，由于精度损失，还原后的序列可能与原序列有微小误差。在对精度要求极高的科学计算中，需要特别注意这一点。

2.3 自定义操作的语义要求

虽然标准没有强制要求，但为了使partial_sum的行为符合直觉且有用，你传入的自定义二元操作op最好满足结合律。这是因为partial_sum的计算过程本质上是左结合的顺序计算：op(op(op(a, b), c), d)。如果操作不满足结合律，那么计算结果将严格依赖于这个特定的从左到右的计算顺序，其意义可能会变得难以理解，也几乎无法与其他算法（如std::reduce）的结果关联。

此外，操作应该尽可能无副作用，并且不使迭代器失效。这是所有STL算法对函数对象的基本要求。

3. 实战技巧：超越前缀和的高级应用模式

掌握了核心机理，我们就可以跳出“计算前缀和”的框框，探索partial_sum在一些更巧妙场景下的应用。这些模式往往能简化代码逻辑，提升表达力。

3.1 状态机与流式解析

这是partial_sum非常强大的一类应用。想象一下，你正在解析一个日志文件，需要将连续的行合并成一个个完整的“事务块”，事务的开始由某个特定标记决定。或者，你需要处理一个信号序列，当累积值超过某个阈值时触发一个事件。

我们可以把“当前是否处于一个事务中”或“当前累积值”看作一个状态。partial_sum的“基于前序结果和当前输入计算新结果”的模式，完美契合状态机的更新逻辑。

假设我们有一个整数序列，代表每日的现金流（正为收入，负为支出）。我们想找出累积余额首次超过100的日期。

std::vector<int> daily_flow = {30, -10, 50, 20, -5, 60}; std::vector<int> balance(daily_flow.size()); auto find_first_over_100 = std::partial_sum( daily_flow.begin(), daily_flow.end(), balance.begin(), std::plus<int>() // 默认加法，计算累积余额 ); // 现在 balance = [30, 20, 70, 90, 85, 145] // 我们可以用 std::find_if 在 balance 中寻找第一个 >100 的元素

在这个例子里，状态就是“累积余额”，partial_sum帮我们高效地完成了所有中间状态的计算。如果规则更复杂，比如余额低于0时重置为0（模拟“不透支”），我们只需自定义op：

auto op = [](int prev_balance, int today_flow) { int new_balance = prev_balance + today_flow; return new_balance > 0 ? new_balance : 0; // 重置逻辑 }; std::partial_sum(daily_flow.begin(), daily_flow.end(), balance.begin(), op);

3.2 生成复杂序列（如阶乘、累乘）

这是对默认加法操作的直接扩展。除了前面提到的累乘，你还可以生成更复杂的序列。例如，生成一个序列，其中每个元素是前一个元素乘以一个系数再加上一个增量（这类似于线性同余生成器的一种形式，或某种滤波器的实现）：

std::vector<double> seq(10); double init = 1.0; double coeff = 0.9; double increment = 0.1; // 第一个元素特殊处理 if (!seq.empty()) seq[0] = init; // 从第二个元素开始应用规则 auto generator = [coeff, increment](double prev, double /* 忽略输入，我们用它来驱动次数 */) { return prev * coeff + increment; }; // 技巧：输入一个无关紧要的序列（如全0）来驱动生成次数 std::vector<int> dummy_input(seq.size() - 1, 0); std::partial_sum(dummy_input.begin(), dummy_input.end(), seq.begin() + 1, generator); // seq 现在是一个根据自定义递推公式生成的序列

这个技巧的关键在于，我们利用了partial_sum会遍历输入区间N-1次（从第二个输出开始）的特性，用一个“哑元”输入来触发N-1次状态转换函数generator的调用。输入值本身被忽略，我们只关心状态（前一个输出值）的迭代更新。

3.3 与std::inclusive_scan和std::exclusive_scan的对比与选择

在C++17之后，<numeric>头文件引入了std::inclusive_scan和std::exclusive_scan。它们和partial_sum功能相似，但存在重要区别：

如何选择？

• 需要并行化加速大数据处理：毫不犹豫选择inclusive_scan或exclusive_scan，并指定std::execution::par执行策略。partial_sum是纯顺序的。
• 操作不满足结合律：只能使用partial_sum，因为scan系列要求结合律。
• 需要“排除当前元素”的前缀和：使用exclusive_scan，它的语义更清晰。用partial_sum模拟exclusive_scan需要偏移输入输出，容易出错。
• 代码需要兼容C++17之前的标准：只能使用partial_sum。
• 简单顺序计算，且不关心并行：两者都可以，partial_sum更通用（不要求结合律），inclusive_scan的命名在表示“包含当前元素”时更清晰。

一个exclusive_scan的典型例子是计算“排他性”前缀和，常用于并行算法如并行排序的前期准备：

std::vector<int> data = {1, 2, 3, 4}; std::vector<int> excl_prefix(data.size()); // 计算 exclusive scan，初始值为0 std::exclusive_scan(data.begin(), data.end(), excl_prefix.begin(), 0); // excl_prefix 结果为 [0, 1, 3, 6] (0, 0+1, 0+1+2, 0+1+2+3)

4. 性能考量、常见陷阱与最佳实践

在实际工程中使用std::partial_sum，了解其性能特点和可能踩的坑，能让你写出更健壮、更高效的代码。

4.1 迭代器失效与原地计算

partial_sum允许输出迭代器与输入迭代器指向同一个区间，即“原地”计算。这是一个非常方便的特性，但必须小心处理。

std::vector<int> vec = {1, 2, 3, 4}; std::partial_sum(vec.begin(), vec.end(), vec.begin()); // 原地计算 // vec 变为 [1, 3, 6, 10]

陷阱：原地计算时，算法会读取一个位置，然后立即写入这个位置或之后的位置。只要写入操作不会覆盖尚未被读取的输入元素，就是安全的。对于partial_sum，由于输出总是基于前一个输出和当前输入，而“当前输入”在计算其对应输出时会被立即读取，因此只要输出迭代器不领先于输入迭代器，原地操作就是安全的。事实上，partial_sum要求输出区间不能与输入区间重叠，除非d_first == first，即原地计算。其他形式的重叠（如输出区间是输入区间的子集且不是从头开始）会导致未定义行为。

最佳实践：如果确定要覆盖原数据，明确使用原地计算，代码意图清晰。如果需要保留原数据，务必确保输出区间有足够的空间，且不与输入区间（除原地外）重叠。

4.2 自定义操作的成本与副作用

自定义操作op会被频繁调用（N-1次）。如果op是一个成本很高的函数（例如涉及动态内存分配、复杂计算、IO操作），那么partial_sum的整体性能就会成为瓶颈。

• 性能建议：尽量保持op轻量。如果操作复杂，考虑能否在调用partial_sum前对数据进行预处理，或者使用更专门的算法。
• 副作用警告：op不应有可观察的副作用，尤其不能修改输入序列或外部状态。STL算法通常假设函数对象是无副作用的，违反这个约定可能导致在不同标准库实现或优化级别下得到不同的结果。例如，在op里修改一个全局计数器是不安全的。

4.3 浮点数的精度累积问题

这是所有基于累积的算法（包括accumulate）的共性问题。由于浮点数的精度限制和舍入误差，多次连续运算的累积误差可能会放大。

std::vector<double> vals(10000, 0.1); // 1万个0.1 std::vector<double> prefix_sum(vals.size()); std::partial_sum(vals.begin(), vals.end(), prefix_sum.begin()); // 理论上，prefix_sum的最后一个元素应该是1000.0 // 但实际上，由于浮点误差，它可能是一个接近1000.0但略有差异的值，如999.999999999999

应对策略：

1. 理解并接受：对于大多数应用，微小的误差在可接受范围内。
2. 使用更高精度：如果可行，使用long double。
3. 改变计算顺序：对于满足结合律的加法，理论上误差与计算顺序有关，但partial_sum是固定顺序。对于超大规模数据，可以考虑使用inclusive_scan配合并行化，然后对并行块的结果进行补偿（如Kahan求和算法），但这需要更复杂的实现。
4. 关键比较时使用容差：用std::fabs(a - b) < epsilon而不是a == b。

4.4 空区间与单元素区间的处理

这是一个边界情况，但良好的代码必须处理。根据标准，如果输入区间为空（first == last），partial_sum将直接返回d_first，不做任何操作。如果输入区间只有一个元素，那么输出区间也只有一个元素，其值等于输入区间的第一个元素，自定义操作op不会被调用。

在编写通用代码时，应当考虑这些情况。例如，在计算前缀和之前，如果容器可能为空，后续使用前缀和结果进行索引访问（如prefix[r] - prefix[l-1]）就会出错。安全的做法是在使用结果前检查容器大小，或者像许多算法书中所教的那样，在前缀和数组前额外插入一个0作为哨兵，使公式统一为prefix[r+1] - prefix[l]，这能有效避免许多边界判断。