c++ - 带有更新的加权随机数生成器

我的问题是这个问题的扩展:Weighted random numbers

扩展名:允许用户动态更改给定键的权重。
如何最佳地解决问题？
天真的解决方案可能是扫描所有元素，根据新的权重调整所有元素的权重……但这是更新的O(n)。这是非常低效的。我们如何做得更好？
我希望update(key, w)和get()优于或等于O(logn)

最佳答案

一种可能的解决方案来自算术编码和Fenwick trees。

如果您有一个非负数列表，即[a_0, ... a_n]类型的T，则Fenwick树数据结构允许您在O(log n)时间内实现以下两个功能:

Index upper_bound(T p):对于给定的p值，计算最小索引i，以使前缀和a_0 + ... + a_i > p相加。

set(Index i, T p):更新a_i <- p。

生成随机i的算法很简单:生成均匀分布在k范围内的随机数[0, sum a_i)，然后使用i = upper_bound(k)查找i。

简单的例子:

i            0 1 2 3 4 5 6 7
a_i          0 1 0 0 3 4 0 2
prefix_sum   0 1 1 1 4 8 8 10

k                   0 1 2 3 4 5 6 7 8 9
i = upper_bound(k)  1 4 4 4 5 5 5 5 7 7

P.Fenwick. A New Data Structure for Cumulative Frequency Tables(PDF，1994年)

My C++ implementation of a Fenwick tree(未经彻底测试)