Random Pick with Weight without repetition

Random Pick with Weight 的变形， 要求根据weight来random 选出 一个item， 下一次random 选出item 的时候根据剩下的items的weights来实现概率的选取，不能output之前已经output过的item。

比如 a:1, b:1,c:3,d;5

d有50%的概率被第一次选出， 如果第一次选的是d，

下一次random 的时候剩下的有a:1, b:1,c:3，  a 有20%的机率被选到。。

最后的item有100%的概率被选到。

考官提示tree结构的解法。。但是我不知道是不是binary search tree还是怎么弄个selection tree.

每次poll出一个item之后，是不是得重新更新tree还是怎么样。。请教各位大神有没什么好的解法。。谢谢！

感觉这题挺麻烦的，像是 Random Pick with Weight + Random Flip Matrix的结合。不仅要维护区间，还要 remapping 区间，不好做。用普通的 balanced tree 最坏情况和每次重建一棵树的复杂度一样。

我能想到的最好的办法是线段树，每个 key 对应一个区间，统计区间内有效的区间长度和，根据左右子树的长度和的比例决定跳左子树或右子树的概率。每次 pick 一个 key 以后就删除对应区间。查找和区间删除的运行时间都是 O(log n) (n 是所有权重之和)。但正常公司（哪怕是google）不会考线段树吧？
p.s. 随手查了查，好像的确有一些面试官会考这玩意儿……有毒