选择概率与其值成比例且小于O（n）的数字的数据结构

Question

我有一组数字，[1,3,4,5,7]。我想从集合中选择一个概率与其值成正比的数字：

然而，我希望能够在不到O（n）的时间内更新和查询这个集合。是否有任何数据结构可以帮助我实现这一点？

最好是在Java，如果它已经存在

Answer 1

您可以使用二叉索引树（也称为Fenwick树）进行分期查询和更新（包括删除/插入元素）。其思想是使用动态调整大小，这与在可变大小数组和哈希表中使用的获得摊销固定时间附加值的技巧相同。这还意味着您应该能够使用从动态数组中重建第二个数组的方法来获得O（logn）最坏情况的边界，但这会使代码明显变长。

首先，我们知道，给定arr的部分和列表，以及[0，sum（arr）]中的一个随机整数，我们可以在O（logn）时间内通过二进制搜索来实现这一点。具体来说，如果我们的随机整数是r，我们希望最右边部分和的索引小于或等于r。

现在，我们将使用Fenwick树的这篇文章中的技术来维护和查询部分和。那篇帖子与你的略有不同：他们有一组固定的n键，它们的权重可以更新，无需新的插入或删除。

Fenwick树是一个数组，允许您在每次查询的O（logn）time中回答有关“基”数组部分和的查询，并且可以在O（n）time中构建。尤其是，你可以

1. 求arr小于或等于r，
2. 对于任何整数c，将arr[i]设置为arr[i]c

都在O（log n）时间。

首先将n零添加到arr（它现在是半满的），然后构建它的芬威克树。我们可以将“删除”元素视为将其权重设置为0。插入一个元素是通过将arr中最右边的非零元素后面的零作为新元素的位置来完成的。移除的元素和新元素最终可能会导致我们的阵列填满：如果我们达到75%的容量，重建我们的阵列和Fenwick树，将阵列大小加倍（在右边用零填充）并删除所有零权重元素。如果我们达到25%的容量，将阵列缩小到一半大小，同时重建芬威克树。

您需要不断维护arr才能重建，因此所有更新都必须在arr和芬威克树上完成。您还需要一个从数组索引到密钥的哈希映射，以便进行随机选择。

好的一面是，您根本不需要修改Fenwick树内部：给定Java中支持初始化、数组更新和二进制搜索的Fenwick树实现，您可以将其视为黑盒。如果您想要最坏情况下的时间保证，这就不再是真的了：然后，您需要一点一点地复制Fenwick树的内部状态，这有一些复杂性。