C++如何使用std::partial_sum计算前缀和-C++-PHP中文网

std::partial_sum不会自动修改原容器，是否修改取决于输出迭代器指向位置：指向原容器则原地更新，指向新容器则保留原数据；严格前缀和需手动偏移，如首项置0后计算；支持自定义二元操作，但需注意结合律影响语义。

c++如何使用std::partial_sum计算前缀和

std::partial_sum 会修改原容器吗？

不会自动修改原容器，但它的输出迭代器可以指向原容器起始位置——这时就变成“原地计算”。关键看第三个参数（输出迭代器）怎么传：std::partial_sum 本身只读输入范围，写入完全由你指定的目标位置决定。

常见误操作是传 vec.begin() 还以为安全，结果覆盖了原始数据。如果想保留原数组，必须另开空间或确保目标区域不重叠（除非你明确要原地更新）。

想保留原数据 → 输出到新容器：std::vector<int> prefix(vec.size()); std::partial_sum(vec.begin(), vec.end(), prefix.begin());</int>
想原地覆盖 → 输出到自身：std::partial_sum(vec.begin(), vec.end(), vec.begin());（此时 vec 变成前缀和数组）
重叠但非起点（如 vec.begin()+1）→ 行为未定义，别这么干

如何用 std::partial_sum 计算「严格前缀和」（不含当前元素）？

std::partial_sum 默认计算的是「含当前元素」的累积和（即 a[0], a[0]+a[1], a[0]+a[1]+a[2]…），也就是通常说的前缀和数组 prefix[i] = sum(a[0..i])。若你需要类似 prefix[i] = sum(a[0..i-1])（即 prefix[0] == 0），得手动偏移。

最稳妥做法：先构造一个首项为 0 的新序列，再对它调用 partial_sum（但注意这不是直接用原数组）；或者更常用的是——先 push_back(0)，再对 [0, end-1) 做 partial_sum 到目标位置。

C++ 算法竞赛自动化测试数据生成与校验框架

根据原题生成新题面、验证器及完整测试数据，自动套用 testlib 模板，用于用户要求生成测试数据时。

下载

推荐方式（安全、清晰）：std::vector<int> prefix = {0}; prefix.reserve(vec.size() + 1); std::partial_sum(vec.begin(), vec.end(), std::back_inserter(prefix));</int>
如果坚持用原数组长度且首项为 0：prefix[0] = 0; std::partial_sum(vec.begin(), vec.end()-1, prefix.begin()+1);（需确保 vec 非空）

自定义二元操作符：不只是加法

std::partial_sum 第四个参数允许传入任意二元函数对象，所以它不只算和，还能算积、最大值、字符串拼接等。但要注意结合律不是强制要求，只是影响语义合理性——比如用 std::min 是合法的，结果是每个位置的前缀最小值；但用减法就不对，因为 a - b - c ≠ a - (b - c)，而 partial_sum 按左结合顺序应用操作符。

前缀积：std::partial_sum(vec.begin(), vec.end(), out.begin(), std::multiplies<int>{});</int>
前缀最大值：std::partial_sum(vec.begin(), vec.end(), out.begin(), [](int a, int b) { return std::max(a, b); });
错误示范（逻辑错，非语法错）：std::minus<int>{}</int> —— 它算的是 a-b, (a-b)-c, ((a-b)-c)-d，不是你想的“差分逆运算”

与手写循环比，partial_sum 有什么实际影响？

性能上，std::partial_sum 通常是优化过的（可能向量化），尤其在大数组上比朴素 for 循环略快；语义上更明确，减少边界错误。但它不检查溢出，也不处理 NaN/Inf（浮点场景下需自行防护）。

兼容性没问题：C++98 起就支持，所有主流 STL 实现都完整实现。唯一容易被忽略的是——它要求输入迭代器是 InputIterator，因此不能直接对 std::list 的 begin() 做原地更新（因为 list::iterator 不是 RandomAccessIterator，但 partial_sum 并不要求随机访问，只要求可递增和解引用；真正限制在于：如果你输出到 list 自身，插入/赋值行为可能低效或不可行）。

对 std::vector / std::array：放心用，性能好
对 std::list：可读取，但输出建议到 vector；原地写 list 效率差，且 list::iterator 不支持 it + n，某些偏移操作写起来麻烦
对 C 风格数组：支持，用 std::partial_sum(a, a+n, out) 即可

最容易被忽略的一点：它不初始化输出容器。如果输出迭代器指向未初始化内存（比如用 reserve 但没 resize 的 vector），行为未定义。务必确保目标空间已分配且可写。