一、accumulate：累加（本节实例08 的主角）

先看它最简单的样子：

#include <iostream>
#include <vector>
#include <numeric>              // ★ 别忘了这个头文件！
using namespace std;

int main() {
    // ── 实例08：用 accumulate 累加元素值 ──
    vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    int sum = accumulate(v.begin(), v.end(), 0);        // ★ 第三个参数是"初始值"
    cout << "1 到 10 的和：" << sum << endl;

    // ── 换个初始值 ────────────────────────
    int sum2 = accumulate(v.begin(), v.end(), 100);
    cout << "初值给 100 再加：" << sum2 << "（100 + 55）" << endl;

    // ── 累乘（用第 4 个参数换个"运算"）──────
    int product = accumulate(v.begin(), v.end(), 1, multiplies<int>());
    cout << "1 到 10 的乘积：" << product << "（10! = 3628800）" << endl;

    // ── 累加一个"部分区间" ─────────────────
    int mid = accumulate(v.begin() + 2, v.begin() + 5, 0);   // 只加 3、4、5
    cout << "第 3～5 个元素的和：" << mid << endl;

    // ── 累加到 string 上（能拼接！）────────
    vector<string> words = {"C++", " ", "是", " ", "门", "好", "语言"};
    string sentence = accumulate(words.begin(), words.end(), string(""));
    cout << "拼出来的句子：" << sentence << endl;
    return 0;
}

看到什么算成功：

1 到 10 的和：55
初值给 100 再加：155（100 + 55）
1 到 10 的乘积：3628800（10! = 3628800）
第 3～5 个元素的和：12
拼出来的句子：C++ 是门好语言

四个要点：

最后那一行的小坑：accumulate(words.begin(), words.end(), "") 编译不过。因为 "" 是 const char*，而 const char* + string 不是合法的累加（而且指针加法会变成"移动指针"）。必须显式写 string("") —— 这也是"初值决定类型"的一个实例。

二、这一节最重要的坑：初值的类型

accumulate 的结果类型 = 初始值的类型（不是元素类型）。这是个"安静出错"的坑：

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int main() {
    vector<double> prices = {1.5, 2.7, 3.3, 4.1};     // 一共 11.6

    // ── ❌ 错误写法：初值给 0（int）──
    double wrong = accumulate(prices.begin(), prices.end(), 0);
    cout << "初值 0（int）：  " << wrong << "   ← 每次相加都被截断！" << endl;

    // ── ✅ 正确写法：初值给 0.0 ──
    double right = accumulate(prices.begin(), prices.end(), 0.0);
    cout << "初值 0.0（double）：" << right << "   ← 正确" << endl;

    // ── 为什么会这样：类型是"初值的类型" ────
    cout << "-- 拆开看 --" << endl;
    cout << "0     + 1.5 = " << (0     + 1.5) << "  （int + double → 转成 double）" << endl;
    cout << "但 accumulate 内部是「把结果存回初值类型」，所以要这样理解：" << endl;
    cout << "  int 型的结果变量：依次 0 → 1 → 3 → 6 → 10（每次 1.5/2.7... 都被截成 1/2/3）" << endl;
    cout << "  所以最后得到 " << wrong << "，而不是 " << right << endl;
    return 0;
}

看到什么算成功：

初值 0（int）：  10   ← 每次相加都被截断！
初值 0.0（double）：11.6   ← 正确
-- 拆开看 --
0     + 1.5 = 1.5  （int + double → 转成 double）
但 accumulate 内部是「把结果存回初值类型」，所以要这样理解：
  int 型的结果变量：依次 0 → 1 → 3 → 6 → 10（每次 1.5/2.7... 都被截成 1/2/3）
  所以最后得到 10，而不是 11.6

机理说清楚：accumulate 的内部差不多是这样：

T accumulate(It first, It last, T init) {      // ★ 返回类型 = 初值的类型 T
    for (; first != last; ++first)
        init = init + *first;                   // ★ 每次赋值都"转回 T"
    return init;
}

所以 init 是 int 时，每次 init + 1.5 算出的 double 都要"塞回 int"——被截断。 加上 2.7、3.3、4.1 各自的截断，最后就得到 10 而不是 11.6。

这正好是 12.1 讲的"模板参数 T 一旦确定，它就是严格类型检查的普通函数" 的又一体现：T 被推导成 int（因为初值是 0），后面就没有任何"自动升级类型"的机会。 同一类坑在 12.4 小结的 Stats<T,size>::average() 里出现过（sum() 是 int，不转 double 就会整数除法）。"累加要用浮点，初值就得写浮点"——这条要写进肌肉记忆。

三、另外三个数值算法

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

void show(const char *t, const vector<int> &v) {
    cout << t << "：";
    for (int x : v) cout << x << " ";
    cout << endl;
}

int main() {
    vector<int> a = {1, 2, 3, 4, 5};
    vector<int> b = {10, 20, 30, 40, 50};

    // ── ① inner_product：内积（对应位置相乘再相加）──
    int ip = inner_product(a.begin(), a.end(), b.begin(), 0);
    cout << "内积 = " << ip << "（1*10 + 2*20 + 3*30 + 4*40 + 5*50 = 550）" << endl;

    // ── ② partial_sum：前缀和（每一项是"到这儿为止的和"）──
    vector<int> ps(5);                              // ★ 目标要有空间
    partial_sum(a.begin(), a.end(), ps.begin());
    show("原数据      ", a);
    show("前缀和      ", ps);

    // ── ③ adjacent_difference：相邻差（后一个减前一个）──
    vector<int> ad(5);
    adjacent_difference(a.begin(), a.end(), ad.begin());
    show("相邻差      ", ad);
    //   第一个元素是"原样复制"，之后每个是"与前一个的差"

    // ── ④ 实用：前缀和能秒答区间和 ──────────
    cout << "-- 用前缀和计算区间 [1,3] 的和 --" << endl;
    cout << "  直接算：2 + 3 + 4 = " << (a[1] + a[2] + a[3]) << endl;
    cout << "  用前缀和：ps[3] - ps[0] = " << (ps[3] - ps[0]) << "（一次减法）" << endl;
    cout << "  （这就是区间和查询能变 O(1) 的原理）" << endl;
    return 0;
}

看到什么算成功：

内积 = 550（1*10 + 2*20 + 3*30 + 4*40 + 5*50 = 550）
原数据      ：1 2 3 4 5 
前缀和      ：1 3 6 10 15 
相邻差      ：1 1 1 1 1 
-- 用前缀和答"第 2 到第 4 个的和" --
  直接算：2 + 3 + 4 = 9
  用前缀和：ps[3] - ps[0] = 9（一次减法）
  （这就是"区间和查询"能变 O(1) 的原理）

三个算法的"读法"：

partial_sum 的实战价值："区间和"从 O(n) 变成 O(1)。预处理一次前缀和，之后每次"求 [i, j] 区间和"都是 ps[j] - ps[i-1]。 这是算法题里最常用的预处理技巧之一，也解释了为什么这个函数值得进标准库。

四、动手 Demo：成绩统计（数值算法版）

任务：把 13.1.1 / 13.3.1 手写过的那份成绩统计，改用数值算法写一遍，体会差别。

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;

int main() {
    vector<int> scores = {88, 95, 72, 88, 60, 95, 88, 100, 55};

    cout << "成绩（" << scores.size() << " 人）：";
    for (int s : scores) cout << s << " ";
    cout << endl;

    // ① 总分：accumulate（替代手写 for 循环）
    int total = accumulate(scores.begin(), scores.end(), 0);
    cout << "① 总分 = " << total << endl;

    // ② 平均分：★ 注意 (double) 转换！
    double avg = (double)accumulate(scores.begin(), scores.end(), 0) / scores.size();
    cout << "② 平均 = " << avg << "（必须转 double，否则整数除法）" << endl;

    // ③ 平均分：★ 更好的写法 —— 初值给 double，省掉转换
    double avg2 = accumulate(scores.begin(), scores.end(), 0.0) / scores.size();
    cout << "③ 平均 = " << avg2 << "（初值 0.0，结果自然就是 double）" << endl;

    // ④ 前缀和 → 任意区间的和都是 O(1)
    vector<int> ps(scores.size());
    partial_sum(scores.begin(), scores.end(), ps.begin());
    cout << "④ 前缀和（前 5 个）：";
    for (int i = 0; i < 5; i++) cout << ps[i] << " ";
    cout << endl;

    // 查"第 4 到第 7 个人的总分"（下标 3~6）
    cout << "   第 4~7 人的总分：ps[6] - ps[2] = " << (ps[6] - ps[2]) << endl;
    cout << "   （手算验证：" << scores[3] << "+" << scores[4] << "+" << scores[5]
         << "+" << scores[6] << " = " << (scores[3] + scores[4] + scores[5] + scores[6]) << "）" << endl;

    // ⑤ 分数波动：相邻差（谁比谁高了）
    vector<int> diff(scores.size());
    adjacent_difference(scores.begin(), scores.end(), diff.begin());
    cout << "⑤ 相邻差（第一个人为原值）：";
    for (int d : diff) cout << d << " ";
    cout << endl;

    // ⑥ 算"加权总分"：每人权重不同 → inner_product
    vector<int> weight = {1, 1, 1, 1, 1, 1, 1, 1, 1};      // 全 1 就是普通总分
    cout << "⑥ 权重全 1 时：inner_product = "
         << inner_product(scores.begin(), scores.end(), weight.begin(), 0)
         << "（应该等于总分 " << total << "）" << endl;
    return 0;
}

看到什么算成功：

成绩（9 人）：88 95 72 88 60 95 88 100 55 
① 总分 = 741
② 平均 = 82.3333（必须转 double，否则整数除法）
③ 平均 = 82.3333（初值 0.0，结果自然就是 double）
④ 前缀和（前 5 个）：88 183 255 343 403 
   第 4~7 人的总分：ps[6] - ps[2] = 331
   （手算验证：88+60+95+88 = 331）
⑤ 相邻差（第一个人为原值）：88 7 -23 16 -28 35 -7 12 -45 
⑥ 权重全 1 时：inner_product = 741（应该等于总分 741）

④ 里最值得记的不是结果，是"下标换算"： - "第 4 到第 7 个人" = 下标 3、4、5、6（"第 N 个"的下标是 N-1）； - 区间 [i, j] 的和 = ps[j] - ps[i-1]（i > 0 时）； - 所以这里是 ps[6] - ps[2]（ps[2] 是"前 3 个人的和"，减掉它剩下的正好是第 4~7 人）。

区间 [i, j] 的和 = ps[j] - ps[i-1] （i > 0 时） 区间 [0, j] 的和 = ps[j]

"下标从 0 数、第几个从 1 数"这个错位是编程里最常见的错误来源之一。 前面 lower_bound / upper_bound 算下标、13.4.1 里算位置，都会再碰到它。

30 秒实验

1. 初值类型实验（本节第一课）：vector<double> prices = {1.5, 2.7, 3.3, 4.1}; 分别用初值 0 和 0.0 跑 → 10 vs 11.6。这一条必须亲眼看一次。
2. 忘记 <numeric>：把 #include <numeric> 注释掉 → 报 'accumulate' was not declared in this scope。记住它在 <numeric> 而不是 <algorithm>。
3. string 拼接的初值：写 accumulate(words.begin(), words.end(), "") → 编译不过；改成 string("") 就好了。
4. partial_sum 目标要有空间：vector<int> ps;（空的）然后 partial_sum(a.begin(), a.end(), ps.begin()); → 崩溃（和 13.3.2 的 copy 同理）。要先 vector<int> ps(a.size()); 或用 back_inserter（13.4.1）。

常见误区

1. "accumulate 在 <algorithm> 里"——在 <numeric> 里。忘了 include 就报"未声明"。
2. "初值随便给 0 就行"——0 是 int，结果就是 int。要浮点结果，初值写 0.0。 这是本节第一大坑，也是"安静的错"（编译没问题、结果错）。
3. "accumulate 只能做加法"——第四个参数能换运算（multiplies<int>()、minus<int>()、自定义的函数对象 / lambda）。换运算时那个"初始值"要对应改（做乘法初值给 1，不能给 0）。
4. "accumulate 只能加数字"——string 能拼（初值给 string("")），自定义类也能（只要那个"累加"操作有定义）。
5. "partial_sum / adjacent_difference 会自己造好输出容器"——不会（算法改不了容器大小）。目标必须提前有空间（或配 back_inserter）。
6. "平均分直接 accumulate(...) / n"——要提防整数除法（和 12.4 小结的 average() 同一个坑）。两种正确写法：(double)accumulate(...,0) / n 或 accumulate(..., 0.0) / n。
7. "数值算法就是给数字用的"——名字叫"数值"，但它只是"把整段折成一个值"的操作：拼字符串、求最大、累积自定义对象都能用它。判断标准是"我要把一段区间压成一个结果吗"。

• ☐ 下一节（13.4 迭代器）

相关笔记

• 排序算法（含实例07） —— 上一节：sort 与二分查找
• 迭代器 —— 下一节：算法与容器之间的那个"插头"
• 算法 —— 四类算法的地图（本节的 <numeric> 在最后一行）
• 修正序列算法（含实例05、06） —— copy 到空容器也会崩（同一个原因）
• 有界数组模板 —— 那个 average() 的整数除法坑
• 小结 —— 小结里同样的"整数除法"提醒
• 🔷 C++基础 · 索引 —— 全课路线图