我有100,000个对象的列表。每个列表元素都有一个与之关联的“权重”，它是从1到N的正整数。
从列表中选择随机元素的最有效方法是什么？我希望我的随机选择元素的分布与列表中权重的分布相同。
例如，如果我有一个列表L = {1,1,2,5}，那么我希望平均选择第5个元素的时间来选择第4个元素。
假定此列表上的插入和删除操作很常见，因此任何使用“积分区域表”的方法都需要经常更新-希望有O（1）运行时和O（1）额外内存的解决方案。
您可以使用增强型二进制搜索树来存储元素以及每个子树中权重的总和。这样，您就可以根据需要插入和删除元素和权重。采样和更新每次操作都需要O（lg n）时间，并且空间使用量为O（n）。
通过在[1，S]中生成一个随机整数（其中S是所有权重的总和（S存储在树的根目录中），然后使用为每个子树存储的权重和执行二进制搜索）来完成采样。
