分段累加法是前缀和加二分查找的通俗叫法，用于按权重随机采样：先用std::partial_sum构建严格递增前缀和数组，再用std::uniform_real_distribution生成[0, sum)内随机数，最后以std::upper_bound定位首个大于该值的前缀和索引。
什么是分段累加法（Alias Method 之外的常用解法）
分段累加法不是标准算法名，而是对「前缀和 + 二分查找」这类实现的通俗叫法。它不依赖复杂预处理，适合权重动态变化不频繁、样本量中等（几百到几千）的场景。核心逻辑是：把每个权重映射成数轴上一段连续区间，总长等于所有权重之和；随机生成一个 [0, sum_weights) 内的浮点或整数，再定位它落在哪一段。
用 std::partial_sum 构建前缀和数组
避免手写循环累加出错，C++ 标准库提供 std::partial_sum 直接生成前缀和。注意输入权重应为非负值，且至少有一个正数，否则行为未定义。
- 输入权重向量建议用
std::vector<double></double>或std::vector<int></int>，保持类型一致 - 前缀和数组长度与原权重相同，
prefix[i]表示前i+1个元素的累计和 - 若用整数权重，需确保累加不溢出；用
double可缓解但要注意浮点精度对边界判断的影响
std::vector<double> weights = {2.0, 3.0, 1.0, 4.0};
std::vector<double> prefix(weights.size());
std::partial_sum(weights.begin(), weights.end(), prefix.begin());
// prefix == {2.0, 5.0, 6.0, 10.0}
用 std::upper_bound 定位随机位置
生成 [0, total_sum) 范围内的随机数后，用 std::upper_bound 找第一个严格大于该值的前缀和位置——这个索引就是选中的下标。用 upper_bound 而非 lower_bound 是关键，否则权重为 0 的项可能被跳过或误判。
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 随机数必须是左闭右开区间：
uniform_real_distribution(0.0, total_sum)或uniform_int_distribution(0, total_sum - 1) - 若权重全为整数且用整型前缀和，推荐用整数随机分布，规避浮点比较误差
-
std::upper_bound返回迭代器，需减去begin()得到索引
std::random_device rd; std::mt19937 gen(rd()); std::uniform_real_distribution<double> dis(0.0, prefix.back()); double r = dis(gen); int idx = std::upper_bound(prefix.begin(), prefix.end(), r) - prefix.begin(); // idx ∈ [0, prefix.size())
权重为 0 时的边界行为与性能提醒
如果某个权重是 0，它在前缀和数组中不会“占长度”，但对应元素仍保留在原始容器中。只要前缀和严格递增（即无连续零权重导致相等），upper_bound 就能正确返回首个大于 r 的位置——这意味着权重为 0 的项永远无法被选中，符合预期。
立即学习“C++免费学习笔记（深入）”；
- 每次选择时间复杂度是
O(log n)，构建前缀和是O(n)；若权重频繁变更，应考虑缓存前缀和并在变动时重算 - 不要在循环内反复调用
std::partial_sum；权重不变时，前缀和只需计算一次 - 当
n < 20左右，线性扫描反而比二分更快，可加分支判断
真正容易被忽略的是：随机数分布的右边界必须严格小于总和，否则 upper_bound 可能返回 end()，导致越界访问。务必检查 idx < prefix.size()，尤其在使用浮点时。
