从问题集按衰减概率随机抽取的算法与数据结构咨询

你的需求完全可以通过加权随机抽样（Weighted Random Sampling）结合动态权重衰减规则实现，这是场景化随机选择中很常用的模式，以下是具体实现思路和对应方法：

核心规则对应 #

你设定的权重规则本质是：每个问题的权重为 1/(抽取次数 + 1)——初始状态下所有问题抽取次数为0，权重都是1；每被抽取一次，抽取次数+1，权重按调和级数降低。这种规则能让被选中次数越多的问题，后续被选中的概率逐步降低，同时保留重复选中的可能（权重永远不会降到0）。

实现方案 #

1. 简单遍历实现（小体量场景） #

如果问题数量不多（比如几百个以内），直接用数组存储每个问题的抽取次数即可：

• 每次抽样时，遍历所有问题，计算每个问题的权重w_i = 1/(count_i + 1)，同时算出所有权重总和total_w
• 生成一个0到total_w之间的随机浮点数r
• 再次遍历问题，累加权重值，当累加值超过r时，选中当前问题
• 最后将该问题的count_i加1，完成抽样

这种方法优势是实现简单、无需复杂数据结构，缺点是每次抽样要遍历两次全量数据，数据量大时效率会下降。

2. 高效数据结构实现（大体量/高频抽样场景） #

如果问题数量多（数千甚至上万）或者需要高频抽样，推荐用线段树或**Fenwick树（二叉索引树）**维护权重的前缀和：

• 初始化时，每个叶子节点对应一个问题的初始权重1，非叶子节点存储对应区间的权重总和
• 抽样时，生成0到总权重的随机数r，通过树的二分查找快速定位到对应问题（时间复杂度O(log n)）
• 抽取完成后，计算该问题权重的变化量（从1/(k)变为1/(k+1)，差值为-1/(k(k+1))），更新树中对应节点的数值，同步更新父节点的总和

这种方法的抽样和更新操作都是O(log n)时间复杂度，适合大规模场景下的高效抽样。

补充说明 #

这种权重衰减模式也属于**"厌恶性随机选择"**的一种，核心是通过动态调整权重，既避免高频重复选中同一元素，又不彻底排除重复选中的可能。

内容的提问来源于stack exchange，提问作者AntonOfTheWoods