c++ - 加权随机数 V2（动态情况）

Question

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

加权随机数

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

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

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

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

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

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

编辑当我阅读评论时，我意识到我需要施加额外的条件。每个修改阶段，只有少数（大部分是两个）权重被修改，这些修改也不会改变权重的总和（归一化条件）。

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

Answer 1

我面临同样的问题。我将描述我目前解决它的计划，但将感谢任何其他建议和/或实施指针。

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