别名法可实现o(1)时间复杂度的非均匀随机采样：先o(n)预处理构造alias和prob数组，再通过一次索引访问与伯努利判断完成采样，适用于固定分段的已知概率分布。
如果您需要在 C++ 中生成符合自定义分段概率分布的非均匀随机数，并追求高性能执行效率，则可能面临采样速度慢、内存开销大或精度不足等问题。以下是实现该目标的具体方法：
一、别名法（Alias Method）预处理采样
别名法通过 O(n) 预处理将任意离散概率分布转换为两个长度为 n 的数组，使得每次采样仅需一次均匀随机索引访问和一次伯努利判断，达到 O(1) 时间复杂度。该方法适用于概率质量函数已知且分段数量固定的情形。
1、构造概率向量 p[0..n-1]，确保所有元素非负且总和为 1。
2、初始化 alias 数组与 prob 数组，长度均为 n；创建两个队列 small 和 large，分别存放归一化后小于 1 和大于等于 1 的索引。
3、对每个 i ∈ [0, n)，计算 q[i] = n * p[i]；若 q[i]
4、当 small 与 large 均非空时，取出 small 中一个索引 l 和 large 中一个索引 g；令 prob[l] = q[l]，alias[l] = g，q[g] -= (1 - q[l])；若 q[g]
5、对剩余 q[i] == 1 的索引 i，设 prob[i] = 1，alias[i] = i。
6、采样时：先生成均匀整数 k ∈ [0, n)，再生成均匀浮点 u ∈ [0, 1)；若 u
二、逆变换采样结合线性插值
当输入为分段线性概率密度函数（PDF）时，可预先计算其累积分布函数（CDF）的分段节点并构建查找表，再利用二分搜索定位区间，最后在线性段内执行逆变换，兼顾精度与速度。
1、给定 x₀
2、将 cdf 数组归一化，使 cdf[n] = 1.0。
3、采样时生成 u ∈ [0, 1)，使用 std::lower_bound 在 cdf 数组中查找首个满足 cdf[i] ≥ u 的索引 i。
4、确定前一节点 i−1，计算局部归一化位置：t = (u − cdf[i−1]) / (cdf[i] − cdf[i−1])。
5、对第 i−1 到 i 区间执行线性插值：结果 = x[i−1] + t × (x[i] − x[i−1])。
三、拒绝采样优化变体（带自适应包络）
针对任意形状但有界支持域的分段 PDF，拒绝采样可通过构造分段常数包络函数提升接受率，避免传统单矩形包络导致的低效问题，尤其适合 PDF 存在尖峰或快速衰减的情形。
1、将定义域划分为 m 个子区间 [aⱼ, bⱼ]，j = 0..m−1，每段上取 fⱼ = max{f(x) | x ∈ [aⱼ, bⱼ]}。
2、计算各段面积权重 wⱼ = fⱼ × (bⱼ − aⱼ)，归一化得选择概率 qⱼ = wⱼ / Σwᵢ。
3、采样时：先依 qⱼ 分布随机选段 j；再在 [aⱼ, bⱼ] 上生成均匀 x；最后生成 v ∈ [0, 1)，若 v ≤ f(x)/fⱼ，则接受 x，否则重试。
4、为加速段选择，可构建别名法结构用于 qⱼ 分布，使段选取也为 O(1)。
5、关键提示：fⱼ 必须严格 ≥ f(x) 对所有 x ∈ [aⱼ, bⱼ] 成立，否则破坏采样正确性。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
