从零花钱到考试分数：用 partial_sum 和 iota 轻松搞定累加与编号

想象一下，你每周都会收到零花钱，第一周 10 元，第二周 15 元，第三周 12 元……你想知道“前 1 周一共多少钱”“前 2 周一共多少钱”……这就是前缀和（也称为部分和）。而另一个常见需求是：给班级里的同学按学号排队，学号从 1 连续递增到 N，这就是递增填充。C++ 的 <numeric> 头文件里有两个超好用的工具——partial_sum 和 iota，一个帮你算前缀和，一个帮你快速生成连续编号。它们能让你的代码既简洁又高效。

1. 什么是部分和（前缀和）？为什么它这么重要？

部分和（partial sum），也叫前缀和，是指一个序列中前 k 个元素的和。例如有 5 个同学的考试成绩：

小明：85 分
小红：90 分
小蓝：78 分
小绿：92 分
小紫：88 分

你想知道“前 1 个同学的总分”“前 2 个同学的总分”……直到“前 5 个同学的总分”。手动算一算：

前 k 个同学	分数列表	总分
前 1 个	85	85
前 2 个	85+90	175
前 3 个	85+90+78	253
前 4 个	85+90+78+92	345
前 5 个	85+90+78+92+88	433

这组数字 [85, 175, 253, 345, 433] 就是原始分数的部分和序列。有了它，你就能用 O(1) 的时间知道任意一段连续区间的总分（比如第 2 到第 4 个同学的总分 = 前 4 个总分 - 前 1 个总分 = 345 - 85 = 260）。这个技巧在算法竞赛、数据分析中超级常用。

除了求和，你还可以求前缀积、前缀最大值、前缀最小值，甚至前缀字符串连接——只要定义好“累积规则”就行。

2. C++ 中的 partial_sum：不止求和，还能自定义

2.1 函数原型

#include <numeric>

// 基本版本：计算部分和（加法）
OutputIt partial_sum(InputIt first, InputIt last, OutputIt d_first);

// 自定义版本：使用二元运算 op 进行累积
OutputIt partial_sum(InputIt first, InputIt last, OutputIt d_first,
                     BinaryOperation op);

输入区间 [first, last)：提供原始数据。
输出起始位置 d_first：存放结果，长度至少等于输入区间的长度。
默认操作：加法。第 i 个输出 = 前 i 个输入元素的和。
自定义操作：你可以传一个函数（或 lambda），比如乘法、取最大值等。注意这个函数的第一个参数是到前一个元素为止的累积结果，第二个参数是当前输入元素。

2.2 生活中的例子：用 partial_sum 算零花钱累积

小林的零花钱每月如下：10 元、15 元、12 元、20 元、18 元。他想知道每月结束后自己一共攒了多少钱。

#include <iostream>
#include <vector>
#include <numeric>

int main() {
    std::vector<int> month_money = {10, 15, 12, 20, 18}; // 每月零花钱
    std::vector<int> total(month_money.size()); // 存放累积总额，大小与输入相同

    std::partial_sum(month_money.begin(), month_money.end(), total.begin());

    std::cout << "每月累积零花钱: ";
    for (int m : total) std::cout << m << " ";
    std::cout << std::endl; // 输出: 10 25 37 57 75
    return 0;
}

2.3 自定义操作：前缀积、前缀最大值、前缀最小值

除了求和，还有很多有趣的累积方式。比如：

前缀积：计算 1×2×3×...×n
前缀最大值：记录到当前位置为止的最大值（比如每天最高气温）
前缀最小值：记录到当前位置为止的最小值（比如每周最低体重）

这里用 lambda 表达式来自定义操作。注意 lambda 捕获列表为空（[]），参数为两个 int，返回一个 int。

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm> // for std::max, std::min

int main() {
    // 前缀积
    std::vector<int> nums = {1, 2, 3, 4, 5};
    std::vector<int> prod(nums.size());
    std::partial_sum(nums.begin(), nums.end(), prod.begin(),
                     [](int a, int b) { return a * b; });
    std::cout << "前缀积: ";
    for (int x : prod) std::cout << x << " "; // 输出: 1 2 6 24 120
    std::cout << std::endl;

    // 前缀最大值（比如每天游戏最高得分）
    std::vector<int> daily_scores = {300, 150, 450, 200, 500};
    std::vector<int> max_so_far(daily_scores.size());
    std::partial_sum(daily_scores.begin(), daily_scores.end(), max_so_far.begin(),
                     [](int a, int b) { return std::max(a, b); });
    std::cout << "前缀最大值: ";
    for (int x : max_so_far) std::cout << x << " "; // 输出: 300 300 450 450 500
    std::cout << std::endl;

    // 前缀最小值（比如每天体重新低）
    std::vector<double> weights = {65.5, 64.8, 65.0, 63.9, 64.2};
    std::vector<double> min_so_far(weights.size());
    std::partial_sum(weights.begin(), weights.end(), min_so_far.begin(),
                     [](double a, double b) { return std::min(a, b); });
    std::cout << "前缀最小值: ";
    for (double x : min_so_far) std::cout << x << " "; // 输出: 65.5 64.8 64.8 63.9 63.9
    std::cout << std::endl;

    return 0;
}

注意：自定义操作中的 a 是前一个累积结果（第一个元素时就是第一个输入），b 是当前元素。千万记住顺序不能搞反。

2.4 进阶：原地计算（把结果写回原数组）

partial_sum 允许输出区间和输入区间重叠（甚至完全一样），这样就会直接修改原数组。但你要小心：修改后原数据就丢失了，除非你不再需要它。

std::vector<int> scores = {85, 90, 78, 92, 88};
// 原地计算前缀和：把 scores 变成部分和序列
std::partial_sum(scores.begin(), scores.end(), scores.begin());
// 现在 scores 变成了: 85, 175, 253, 345, 433

2.5 新手容易犯的错误

输出区间长度不够：partial_sum 会写满整个输入区间长度的位置，如果输出容器太小，会导致越界（未定义行为）。务必保证输出容器大小 ≥ 输入容器大小。
自定义操作参数顺序搞混：第一个参数是累积结果，第二个是当前元素。很多人写成 [](int a, int b) { return a + b; } 没问题，但如果是减法 a - b 就变成了累积差，而 b - a 则完全不同。
溢出问题：如果输入都是 int，前缀和可能超过 int 范围（例如 100 万个 10 万相加会达到 10^11，超出 32 位 int）。考虑使用 long long 或更大的类型。

3. iota：一秒生成连续编号

3.1 函数原型

#include <numeric>

void iota(ForwardIt first, ForwardIt last, T value);

把区间 [first, last) 中的元素依次赋值为 value, value+1, value+2, ...
没有返回值（C++17 之前和之后都是 void，不能赋值给迭代器）
要求迭代器支持自增（Forward Iterator）

3.2 生活中的例子：给同学编号

班级有 35 个同学，需要从 1 到 35 编号。用 iota 一行搞定：

#include <iostream>
#include <vector>
#include <numeric>

int main() {
    std::vector<int> student_ids(35); // 存放 35 个学号
    std::iota(student_ids.begin(), student_ids.end(), 1); // 从 1 开始

    std::cout << "学号前10个: ";
    for (int i = 0; i < 10; ++i) std::cout << student_ids[i] << " ";
    std::cout << std::endl; // 输出: 1 2 3 4 5 6 7 8 9 10
    return 0;
}

3.3 如何生成递减序列？或步长不为 1 的序列？

iota 只能生成步长为 1 的递增序列。如果需要递减，可以先生成递增，再 std::reverse：

std::vector<int> v(10);
std::iota(v.begin(), v.end(), 1);   // 1,2,3,...,10
std::reverse(v.begin(), v.end());   // 10,9,8,...,1

如果需要步长为 2 的序列（如 1,3,5,7,...），可以用 std::generate 配合 lambda：

std::vector<int> v(5);
int start = 1;
std::generate(v.begin(), v.end(), [&start]() { int cur = start; start += 2; return cur; });
// v = {1, 3, 5, 7, 9}

或者更简单地，用循环。iota 只负责最简单的情况。

3.4 新手容易犯的错误

忘记给容器预留空间：如果 vector 大小为 0，直接 iota 不会产生任何元素。必须先 resize 或者初始化大小。
把 iota 的返回值当作迭代器：iota 是 void 函数，所以不要写成 auto it = std::iota(...)，那样会编译错误。
步长误解：iota 只支持步长 1。不要试图传步长参数，它没有。

4. Python 中的对应实现：accumulate 和 range

如果你更熟悉 Python，下面这些技巧能让你快速实现相同功能。

4.1 前缀和：itertools.accumulate

import itertools

# 基本前缀和
scores = [85, 90, 78, 92, 88]
prefix = list(itertools.accumulate(scores))
print("前缀和:", prefix)  # [85, 175, 253, 345, 433]

# 自定义前缀积
nums = [1, 2, 3, 4, 5]
prefix_prod = list(itertools.accumulate(nums, lambda a, b: a * b))
print("前缀积:", prefix_prod)  # [1, 2, 6, 24, 120]

# 前缀最大值
heights = [3, 1, 4, 1, 5, 9]
max_prefix = list(itertools.accumulate(heights, max))
print("前缀最大值:", max_prefix)  # [3, 3, 4, 4, 5, 9]

accumulate 默认用加法，也可以传入任何二元函数。注意它的参数顺序和 C++ 一样：第一个是累积结果，第二个是当前元素。

4.2 递增填充：range

Python 的 range 天生就能生成连续整数序列，完全不需要额外的函数。

# 从 1 到 10 的学号
student_ids = list(range(1, 11))
print("学生学号:", student_ids)  # [1,2,3,4,5,6,7,8,9,10]

# 从 0 开始递增
arr = list(range(0, 5))  # [0,1,2,3,4]

# 步长不为 1
even_nums = list(range(2, 11, 2))  # [2,4,6,8,10]

# 递减序列（用 step 为负数）
desc = list(range(10, 0, -1))  # [10,9,...,1]

对比 C++ 的 iota，Python 的 range 更灵活，支持任意起始、任意步长（包括负数）。

4.3 注意：Python 中手动计算前缀和的另一种写法

很多初学者喜欢这样写：

prefix = [0]
for s in scores:
    prefix.append(prefix[-1] + s)
prefix = prefix[1:]  # 去掉开头的 0

这种方法也正确，但不如 accumulate 简洁。accumulate 还会自动处理空列表的情况（返回空列表）。

5. 完整可运行示例：零花钱 + 游戏经验值 + 学号生成

下面这个程序综合展示了 partial_sum（多种自定义操作）和 iota 的用法，并包含了输入输出。

#include <iostream>
#include <vector>
#include <numeric>   // partial_sum, iota
#include <algorithm> // for_each, max, min
#include <string>    // 用于字符串前缀

int main() {
    // ---------- 1. 零花钱累积 ----------
    std::cout << "=== 零花钱累积 ===" << std::endl;
    std::vector<int> allowance = {10, 15, 12, 20, 18};  // 每月零花钱（元）
    std::vector<int> total(allowance.size());            // 存放累积金额
    std::partial_sum(allowance.begin(), allowance.end(), total.begin());
    std::cout << "每月累积零花钱: ";
    for (int t : total) std::cout << t << " ";
    std::cout << std::endl; // 10 25 37 57 75

    // ---------- 2. 游戏经验值的前缀最大值 ----------
    std::cout << "\n=== 游戏经验值最大值（前缀） ===" << std::endl;
    std::vector<int> exp_points = {1200, 800, 1500, 1000, 1800}; // 每局经验
    std::vector<int> max_exp(exp_points.size());
    std::partial_sum(exp_points.begin(), exp_points.end(), max_exp.begin(),
                     [](int a, int b) { return std::max(a, b); });
    std::cout << "到当前局为止的最高经验: ";
    for (int m : max_exp) std::cout << m << " ";
    std::cout << std::endl; // 1200 1200 1500 1500 1800

    // ---------- 3. 前缀积（数学小练习） ----------
    std::cout << "\n=== 前缀积（1~5 的阶乘）===" << std::endl;
    std::vector<int> factorial_input = {1, 2, 3, 4, 5};
    std::vector<int> factorial(factorial_input.size());
    std::partial_sum(factorial_input.begin(), factorial_input.end(), factorial.begin(),
                     [](int a, int b) { return a * b; });
    std::cout << "1! 2! 3! 4! 5! 的值: ";
    for (int f : factorial) std::cout << f << " ";
    std::cout << std::endl; // 1 2 6 24 120

    // ---------- 4. 用 iota 生成学号，然后求学号的前缀和 ----------
    std::cout << "\n=== iota 生成学号并求前缀和 ===" << std::endl;
    std::vector<int> student_id(5);          // 5 个学生
    std::iota(student_id.begin(), student_id.end(), 1); // 学号 1,2,3,4,5
    std::cout << "学号: ";
    for (int id : student_id) std::cout << id << " ";
    std::cout << std::endl; // 1 2 3 4 5

    std::vector<int> id_prefix(student_id.size());
    std::partial_sum(student_id.begin(), student_id.end(), id_prefix.begin());
    std::cout << "学号前缀和: ";
    for (int p : id_prefix) std::cout << p << " ";
    std::cout << std::endl; // 1 3 6 10 15

    // ---------- 5. 自定义操作：前缀字符串连接（字母顺序） ----------
    std::cout << "\n=== 前缀字符串连接 ===" << std::endl;
    std::vector<std::string> words = {"I", "love", "C++", "and", "Python"};
    std::vector<std::string> concat(words.size());
    // 注意：第一个参数是累积结果（字符串），第二个是当前单词
    std::partial_sum(words.begin(), words.end(), concat.begin(),
                     [](const std::string& a, const std::string& b) {
                         return a + " " + b;
                     });
    std::cout << "前缀字符串: ";
    for (const std::string& s : concat) std::cout << "\"" << s << "\" ";
    std::cout << std::endl; // "I" "I love" "I love C++" "I love C++ and" "I love C++ and Python"

    return 0;
}

运行结果：

=== 零花钱累积 ===
每月累积零花钱: 10 25 37 57 75

=== 游戏经验值最大值（前缀） ===
到当前局为止的最高经验: 1200 1200 1500 1500 1800

=== 前缀积（1~5 的阶乘）===
1! 2! 3! 4! 5! 的值: 1 2 6 24 120

=== iota 生成学号并求前缀和 ===
学号: 1 2 3 4 5
学号前缀和: 1 3 6 10 15

=== 前缀字符串连接 ===
前缀字符串: "I" "I love" "I love C++" "I love C++ and" "I love C++ and Python"

6. 常见错误与注意事项（避坑指南）

错误	说明	正确做法
输出容器未分配空间	`vector<int> out; partial_sum(..., out.begin());` 会导致崩溃	用 `resize` 或在构造函数中指定大小
自定义操作参数顺序颠倒	写成了 `[](int b, int a)` 会导致逻辑错误	第一个参数是累积值，第二个是当前元素
iota 后忘记初始化容器大小	`vector<int> v; iota(v.begin(), v.end(), 0);` 不会添加任何元素	先 `v.resize(n)` 或 `vector<int> v(n);`
以为 iota 可以指定步长	`iota(v.begin(), v.end(), 0, 2)` 编译错误	用 `std::generate` 或循环
前缀和溢出	`int` 存不下大和	用 `long long` 或 Python 自动大整数
原地计算时丢失原始数据	`partial_sum(a.begin(), a.end(), a.begin())` 会覆盖原数组	确认不再需要原数据，或使用另开容器

7. 相关知识点指引

差分数组：前缀和的逆运算。如果知道前缀和，想还原原数组，可以用 std::adjacent_difference（也在 <numeric> 中）。
区间求和优化：有了前缀和，你就能用 O(1) 时间求出任意子数组的和（sum[l..r] = prefix[r] - prefix[l-1]）。
二维前缀和：对于矩阵，二维前缀和可以快速求子矩阵的和。实现思路类似，但需要用两层循环手动计算。
iota 与 generate 的区别：iota 生成连续递增，std::generate 可以使用任意函数生成任意序列。
Python 中的累积更多功能：itertools.accumulate 还能接受 initial 参数（Python 3.8+），设置初始值。
其他 <numeric> 算法：inner_product（内积）、adjacent_difference（相邻差）、gcd、lcm（C++17）等。

掌握了 partial_sum 和 iota，你就拥有了一把处理序列累积和编号的瑞士军刀。下次遇到需要“从某数开始连续编号”或“计算前 N 项和”的问题，别再写笨重的循环了，试试这些简洁的 STL 函数吧！

partial_sum部分和与iota递增填充