# 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.

• 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? May 17, 2021 at 15:50

• 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.
All operations can be done in $$O(\log n)$$.