动态加载骰子的数据结构？
Data structure for dynamic loaded dice?
假设我有一个有序的频率列表，例如[1, 1, 2]。我希望能够从这个列表中快速抽样，选择一个选项的概率与其值成正比。
The Alias method 让我们用 O(n) 的构造时间和 O(1) 的查询时间来做这个采样。我对这个问题的版本很感兴趣，我们也支持更新或插入这个列表。
这里有一些想法：
- 一个增强的 BST 可以用 O(log(n)) 的所有操作来做到这一点
- 您可以使用分层数据结构，其中有 n/log(n) 个大小为 log(n) 的块。每个块都存储为一个增强的 BST，顶层数据结构是别名方法。选择一个 BST 需要 O(1)，在其中选择需要 O(log(log(n)))，所以你的查询时间是 O(log(log(n)))。每当发生更新时，您都需要完全重建顶层结构，这需要 O(n/log(n)) 时间。
有没有更快的解决方案？
论文 "Dynamic Generation of Discrete Random Variates" by Matias, Vitter, and Ni 描述了如何在恒定的预期更新和查询时间内执行此操作。这些技术一点都不简单！
假设我有一个有序的频率列表，例如[1, 1, 2]。我希望能够从这个列表中快速抽样，选择一个选项的概率与其值成正比。
The Alias method 让我们用 O(n) 的构造时间和 O(1) 的查询时间来做这个采样。我对这个问题的版本很感兴趣，我们也支持更新或插入这个列表。
这里有一些想法：
- 一个增强的 BST 可以用 O(log(n)) 的所有操作来做到这一点
- 您可以使用分层数据结构，其中有 n/log(n) 个大小为 log(n) 的块。每个块都存储为一个增强的 BST，顶层数据结构是别名方法。选择一个 BST 需要 O(1)，在其中选择需要 O(log(log(n)))，所以你的查询时间是 O(log(log(n)))。每当发生更新时，您都需要完全重建顶层结构，这需要 O(n/log(n)) 时间。
有没有更快的解决方案？
论文 "Dynamic Generation of Discrete Random Variates" by Matias, Vitter, and Ni 描述了如何在恒定的预期更新和查询时间内执行此操作。这些技术一点都不简单！