0
周波数のリストがあるとします（例：[1, 1, 2]）。このリストから、その値に比例したオプションを選択する確率で、すばやくサンプリングできるようにしたい。動的に積み重ねられたサイコロのデータ構造ですか？
The Alias methodこのサンプリングは、O（n）の構築時間とO（1）のクエリ時間で行うことができます。私は、このリストの更新や挿入をサポートしているこの問題のバージョンに興味があります。
- が拡張さBSTは、あなたがn /ログを持っていますが、階層データ構造を使用することができます
- O取ったすべての操作（n個のログを（））、でこれを行うことができます（：ここでは はいくつかのアイデアですn）ブロックのサイズlog（n）。各ブロックは拡張BSTとして格納され、最上位のデータ構造はエイリアス・メソッドです。 BSTを選択するとO（1）が必要になり、その中でO（log（log（n）））を選択すると、クエリ時間はO（log（log（n）））になります。そして、更新が起こるたびに、O（n/log（n））時間かかる最上位構造を完全に再構築する必要があります。
さらに高速なソリューションはありますか？