我有一组数字，[1, 3, 4, 5, 7].我想从集合中选择一个概率与其值成正比的数字：
| Number | Probability | % |
|---|---|---|
| 1 | /20 | 5 |
| 3 | /20 | 15 |
| 4 | /2020 | |
| 5 | /20 | 25 |
| 7 | /20 | 35 |
您可以使用二叉索引树(也称为泛伟树)获得O(log n)摊销查询和更新(包括删除/插入元素)。这个想法是使用动态调整大小，这与可变大小数组和哈希表中用于获得摊销常量时间附加的技巧相同。这也意味着您应该能够使用该方法从侧重建第二个数组的动态数组中获得O(log n)最坏情况的边界，但这会使代码明显更长。
首先，我们知道给定一个arr的部分和的列表，以及一个[0, sum(arr)]中的随机整数，我们可以通过二叉搜索在O(log n)时间内做到这一点。具体来说，如果我们的随机整数是r，我们希望最右边的部分和的索引小于或等于r。
现在，我们将使用这篇芬威克树帖子中的技术来维护和查询部分总和。该帖子与您的帖子略有不同：它们有一组固定的n键，其权重可以更新，而无需新的插入或删除。
泛伟树是一个数组，允许您在每个查询的O(log n)时间内回答有关"基本"数组部分总和的查询，并且可以在O(n)时间内构建。特别是，您可以
- 求
arr最右边的偏和小于等于r的索引， - 将任何整数
c的arr[i]设置为arr[i]+c，
都在O(log n)时间。
首先将n个零附加到arr(它现在是半满的)，然后构建它的芬威克树。我们可以将"删除"元素视为将其权重设置为 0。插入元素是通过将arr中最右边的非零元素后面的零作为新元素的位置来完成的。删除的元素和新元素最终可能会导致我们的数组填满：如果我们达到 75% 的容量，重建我们的数组和 Fenwick 树，将数组大小加倍(右侧为零)并删除所有零权重元素。如果我们达到 25% 的容量，将阵列缩小到一半大小，同时重建芬威克树。
您需要不断维护arr才能重建，因此所有更新都必须在arr和芬威克树上完成。您还需要一个从数组索引到键的哈希图，以便进行随机选择。
好的部分是你根本不需要修改泛伟树的内部：给定Java中支持初始化，数组更新和二叉搜索的泛伟树实现，你可以将其视为一个黑盒。如果你想要最坏情况的时间保证，那就不再是真的了：然后，你需要一点一点地复制芬威克树的内部状态，这有一些复杂性。