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.