exclusive_scan：C++里那个“总差一步”的前缀和

你有没有过这种体验？写完一段累加逻辑，发现结果数组的第 i 项不该包含当前元素——它得“空着”自己，只算前面的。比如计算购物车每件商品的累计优惠（不包含本件），或者生成索引偏移表时要预留首项空间。这时候，std::inclusive_scan 就有点太“热心”了：它把当前元素也塞进去了。而 exclusive_scan，就是那个默默帮你“掐掉尾巴”的人。

它不炫技，不抢镜，但用对了，代码立刻少三层 if 和一个手动补零操作。

exclusive_scan 是 C++17 引入的并行算法之一，定义在 <numeric> 头文件里。名字里的 exclusive 很直白：当前元素不参与本次计算。它的输出序列中，第 0 项是初始值（默认为 0），第 1 项是 input[0]，第 2 项是 input[0] + input[1]，依此类推——每一项都只覆盖“到前一项为止”的累积效果。

最简调用长这样：

std::vector<int> src = {2, 3, 4, 5};
std::vector<int> dst(src.size() + 1); // 注意：输出比输入多一位！
std::exclusive_scan(src.begin(), src.end(), dst.begin(), 0);
// dst → {0, 2, 5, 9, 14}

这里有个实操中容易踩的坑：输出容器必须至少比输入多一个位置。因为 exclusive 扫描天然多出一个“起点占位符”。如果你硬给 dst 分配 src.size() 个元素，程序可能静默越界——尤其在 release 模式下，debug 都难抓。我第一次在嵌入式设备上遇到它崩溃，查了半小时才发现是这个长度错位。

它的完整签名支持自定义二元操作和初始值：

std::exclusive_scan(first, last, d_first, init, binary_op);

其中 binary_op 默认是 std::plus<>()，但你可以换成乘法、最大值、字符串拼接，甚至自定义结构体的合并逻辑。比如你想做“排他性最大值前缀”：

std::vector<int> a = {5, 1, 8, 3};
std::vector<int> max_excl(a.size() + 1);
std::exclusive_scan(a.begin(), a.end(), max_excl.begin(), 
                     std::numeric_limits<int>::min(), 
                     [](int a, int b) { return std::max(a, b); });
// max_excl → {-2147483648, 5, 5, 8, 8}

注意初始值不能设成 0——否则第一个有效值就被污染了。初始值不是“默认值”，而是“哨兵值”，它决定整个扫描的起点语义。

和 inclusive_scan 最本质的区别不在 API，而在数据流节奏：

• inclusive：读 a₀ → 算 a₀ → 写 a₀
• exclusive：读 a₀ → 算（空）→ 写 init；读 a₁ → 算 a₀ → 写 a₀；读 a₂ → 算 a₀+a₁ → 写 a₀+a₁

这个“慢一拍”的特性，让它天然适配偏移类建模。比如构建稀疏矩阵 CSR 格式中的 row_ptr 数组：给定每行非零元个数 {2, 0, 3, 1}，你要得到起始索引 {0, 2, 2, 5, 6}。一行 exclusive_scan 就搞定，不用手写循环+累加器+push_back。

再比如日志系统里按时间分桶：已知每个桶内事件数 {12, 5, 8, 0, 3}，想快速定位第 n 个事件落在哪个桶。先 exclusive_scan 出前缀和边界，再二分查找——整个过程无分支、缓存友好，比逐桶累加快得多。

有人问：那它和 partial_sum 有什么区别？答案很实在：partial_sum 只支持加法，且没有 initial 参数；exclusive_scan 支持任意二元操作、任意初值，并原生支持执行策略（比如 std::execution::par_unseq）。当你需要在多核 CPU 上加速百万级浮点数组的排他前缀乘积时，exclusive_scan 的并行能力就是实打实的吞吐量。

顺带提一句：别指望它自动处理溢出。整数溢出仍是未定义行为。如果业务场景涉及大数累积（比如金融累加），记得配合 std::safe_numerics 或手动检查——算法不替你担责，它只负责把逻辑跑得又快又准。

最后说个调试小技巧：写完 exclusive_scan，别急着跑结果。先拿三元素小数组 {a,b,c} 手算一遍：输出应为 {init, init+a, init+a+b}。对不上？八成是初始值设错了，或是输出空间没多留一位。这个心算验证，5 秒钟的事，能省掉大半 gdb 时间。

exclusive_scan 不是语法糖，它是把“差一位”的工程直觉，固化成标准库里的一个原子操作。它不解决所有问题，但当你再次面对“我要前面的和，不要自己的”这类需求时，脑海里该跳出的，不再是 for 循环和临时变量，而是一个干净利落的函数调用——以及那个恰到好处的、空着的第一格。