c++ - 加权随机数 V2(动态情况)

Question

这个问题是链接下方问题的扩展。

Weighted random numbers

我的问题是对加权随机数进行抽样，附加条件是每个元素的权重经常动态变化。

编辑假设有 N 个元素以不同的权重选择。

对于静态权重，Walker 的别名方法需要 O(N) 时间来设置别名，但采样成本为 O(1)，因此它是实现我的目标的最佳方法之一。

而二分查找法也需要O(N)来制作累积数组，采样成本为log(N)

但是在我的例子中，因为权重经常变化，所以修改权重的时间复杂度也很重要。

所以我想知道现有的库或算法在修改数据结构和采样方面的时间复杂度都小于 O(N)。

编辑 当我阅读评论时，我意识到我需要施加额外的条件。每个修改阶段，只修改少数几个(主要是两个)权重，而且这些修改不会改变权重的总和(归一化条件)。

如果有解决办法，我也想知道当权重也是实数时是否可以使用。

Answer 1

我遇到了同样的问题。我将描述我目前的解决方案，但如有任何其他建议和/或实现建议，我将不胜感激。

我目前的计划是调整动态订单统计的算法，如第 14.1 节所述Cormen/Leiserson/Rivest 的“算法导论”。您将元素放入平衡二叉树中，例如红黑树，以权重作为键。您扩充树，以便每个节点都将权重之和存储在其子树中。然后根存储整棵树的权重总和，比如 S .子树总和可以在树操作期间以与动态订单统计的子树大小相同的方式更新。要进行加权抽样，您可以在 [0..S] 中抽取一个数字。统一地说x ;然后在树下搜索节点 N这样 N 之前的节点的权重总和中序遍历是<x , 但总和加上 N的重量是>x -- 类似于动态订单统计的OS-Select操作。