Randomly selecting element from data structure, probability based on weight

I have a list of elements, each with an id and a weight.

A: The weight should be directly proportional to the probability of being randomly selected: An element with weight 10 should be twice as likely to be selected as an element with weight 5.

B: I need to add/remove elements and increase/decrease their weight dynamically.

I have already found a solution, if I exclude B:

1. fill array with id and weight
2. compute prefix sum
3. generate random number r between 0 and sum of weights - 1
4. binary search which element in the prefix sum corresponds to r

Let n be the number of elements, this solution would be able to retrieve the desired element in O(log(n)), precomputation is O(n). However I cannot add/remove elements or alter their weight without having to precompute the prefix sum again.

Can someone provide me with an approach working for A and B? I have tried using a segement tree but don't find a satisfactory solution.

I think it would work with a complete tree with elements stored in leaves, the whole thing being stored in an array (the same way as for heaps). You also need to store in each node the sum of the weights of all its children.

To be able to modify weight, you would also need a corresponding array (or hashtable if ids are not consecutive integers), to know where in the heap is stored an element with given id.

• To know how to select an element, when exploring the tree t of weight t.weight, you can generate a number r between $0$ and t.weight, and go left if `r

• To insert, just put it at the last available leaf position and modify the weights of all its ancestors.

• To delete, switch the position with the last leaf, and modify the ancestors of both the deleted node and the switched leaf.

• To modify weight, use the corresponding structure to know the position of the element of given id, and modify the weights of its ancestors.

All operations can be done in $O(\log n)$.

StackExchange Computer Science Q#140432, answer score: 5