accumulate、partial_sum、iota —— 来自 <numeric> 头文件的数值类算法，求和、前缀和、批量赋值。
把区间内所有元素累加起来。第三个参数是初始值，同时也决定了返回值的类型。
| 1 | vector<int> v = {1, 2, 3, 4, 5}; |
| 2 | int sum = accumulate(v.begin(), v.end(), 0); |
| 3 | cout << "求和: " << sum << endl; // 求和: 15 |
| 4 | |
| 5 | // 第三个参数是初始值，也是返回值的类型 |
| 6 | long long big_sum = accumulate(v.begin(), v.end(), 0LL); |
0LL 而不是 0，否则结果可能溢出 int。这是因为 accumulate 的返回类型是根据初始值的类型推导的——写 0 就是按 int 一路累加（容易溢出），写 0LL 就是按 long long 累加。同理，如果需要按浮点数累加（比如数组里存的是 double），初始值可以写 0.0，这样 accumulate 就会按 double 类型进行求和——如果这时候误写成 0（整数），累加过程会被强制按 int 计算，小数部分会被直接截断丢失。计算前缀和数组：结果数组的第 i 个元素，等于原数组前 i+1 个元素的总和。竞赛中常用前缀和快速计算"任意区间的和"。
pre[2] = 6 表示 v[0] + v[1] + v[2] = 1 + 2 + 3 = 6。有了前缀和数组，想知道"原数组某一段区间的和"就不用每次重新累加，直接用两个前缀和相减即可（O(1) 查询）。| 1 | vector<int> v = {1, 2, 3, 4, 5}; |
| 2 | vector<int> pre(v.size()); |
| 3 | partial_sum(v.begin(), v.end(), pre.begin()); |
| 4 | // pre 变成 {1, 3, 6, 10, 15} |
copy 类似，partial_sum 也不会自动帮目标容器扩容——写入之前，目标容器必须已经有足够的空间（像例子里 vector<int> pre(v.size()) 那样预先分配好），否则会越界访问。如果不想手动算大小，同样可以用 back_inserter(pre) 代替 pre.begin()。把区间内的元素依次填充成从某个起始值开始、每次加 1 的连续整数。常用于快速生成"下标数组"（比如配合 sort 间接排序时用到的索引序列）。
| 1 | vector<int> v(5); |
| 2 | iota(v.begin(), v.end(), 1); |
| 3 | // v 变成 {1, 2, 3, 4, 5} |
| 4 | |
| 5 | iota(v.begin(), v.end(), 10); |
| 6 | // v 变成 {10, 11, 12, 13, 14} |
iota 生成 {0, 1, 2, ...} 的下标数组，再用自定义比较函数对下标数组 sort，排序依据是 v[下标] 的大小。这样原数组不被破坏，还能拿到排序后的下标顺序。| 1 | vector<int> data = {5, 1, 4, 2, 3}; |
| 2 | vector<int> idx(5); |
| 3 | iota(idx.begin(), idx.end(), 0); // idx = {0, 1, 2, 3, 4} |
| 4 | sort(idx.begin(), idx.end(), [&](int i, int j) { |
| 5 | return data[i] < data[j]; // 排序依据是 data[下标] 的大小，而不是下标本身 |
| 6 | }); |
| 7 | // idx 变成 {1, 3, 4, 2, 0} —— data 中元素从小到大排列时，对应的原始下标 |
[&]——它表示"捕获外部变量 data，按引用使用"，这样比较函数内部才能访问到外面的 data 数组。data 本身自始至终没有被排序或修改，改变顺序的只有 idx。