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.

  • $\begingroup$ It is unfortunate that you use the same designations for requirements and steps: I suggest using letters for the former. Without further requirements, say, regarding resource usage, how does the prefix sum array fall short? If precompute the prefix sum again was unacceptable, tree sounds plausible : what makes you think segment tree? $\endgroup$ – greybeard May 17 at 15:50

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 < t.left.weight and right otherwise.
  • 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)$.

  • $\begingroup$ That answers my question really well, thank you! $\endgroup$ – Moritz_st May 17 at 16:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.