0
假設我有一個有序的頻率列表，例如[1, 1, 2]。我希望能夠從此列表中快速抽樣，選擇與其價值成正比的選項的概率。動態加載骰子的數據結構？
The Alias method讓我們用O（n）構造時間和O（1）查詢時間完成此採樣。我對這個問題的版本感興趣，我們也支持這個列表的更新或插入。
這裏有一些想法：
- 的增強BST可以採取o所有操作（的log（n））
- 您可以使用一個分層的數據結構，在那裏你有N /日誌做到這一點（ n）大小爲log（n）的塊。每個塊存儲爲擴充的BST，頂層數據結構是別名方法。選擇一個BST需要O（1），並且在它內部選擇需要O（log（log（n））），所以你的查詢時間是O（log（log（n）））。每當更新發生時，您需要完全重建頂層結構，這需要O（n/log（n））時間。
有沒有更快的解決方案？