Data structure to achieve random delete and insert where elements are weighted in [a,b]

I don't know if O(1) worst-case time is impossible; I don't see any particular reason it should be. But it's definitely possible to have a simple data structure which achieves O(1) expected time.

The idea is to store a dynamic array of pairs (or two parallel arrays), where each item is paired with its weight; insertion is done by appending in O(1) amortised time, and an element can be removed by index by swapping it with the last element so that it can be removed from the end of the array in O(1) time. To sample a random element from the weighted distribution, choose a random index and generate a random number in the half-open interval [0, 2); if it is less than the element's weight, select the element at that index, otherwise repeat this process until an element is selected. The idea is that each index is equally likely to be chosen, and the probability it gets kept rather than rejected is proportional to its weight.

This is a Las Vegas algorithm, meaning it is expected to complete in a finite time, but with very low probability it can take arbitrarily long to complete. The number of iterations required to sample an element will be highest when every weight is exactly 1, in which case it follows a geometric distribution with parameter p = 1/2, so its expected value is 2, a constant which is independent of the number of elements in the data structure.

In general, if all weights are in an interval [a, b] for real numbers 0 < a <= b, then the expected number of iterations is at most b/a. This is always a constant, but it is potentially a large constant (i.e. it takes many iterations to select a single sample) if the lower bound a is small relative to b.

This is not an answer per se, but just a tiny example to illustrate the algorithm devised by @kaya3

| value | weight |
| v1    | 1.0    |
| v2    | 1.5    |
| v3    | 1.5    |
| v4    | 2.0    |
| v5    | 1.0    |
| total | 7.0    |

The total weight is 7.0. It's easy to maintain in O(1) by storing it in some memory and increasing/decreasing at each insertion/removal.

The probability of each element is simply it's weight divided by total weight.

| value | proba |
| v1    | 1.0/7 | 0.1428...
| v2    | 1.5/7 | 0.2142...
| v3    | 1.5/7 | 0.2142...
| v4    | 2.0/7 | 0.2857...
| v5    | 1.0/7 | 0.1428...

Using the algorithm of @kaya3, if we draw a random index, then the probability of each value is 1/size (1/5 here).

The chance of being rejected is 50% for v1, 25% for v2 and 0% for v4. So at first round, the probability to be selected are:

| value | proba  |
| v1    |  2/20  | 0.10
| v2    |  3/20  | 0.15
| v3    |  3/20  | 0.15
| v4    |  4/20  | 0.20
| v5    |  2/20  | 0.10
| total | 14/20  | (70%)

Then the proba of having a 2nd round is 30%, and the proba of each index is 6/20/5 = 3/50

| value | proba 2 rounds |
| v1    |  2/20 +  6/200 | 0.130
| v2    |  3/20 +  9/200 | 0.195
| v3    |  3/20 +  9/200 | 0.195
| v4    |  4/20 + 12/200 | 0.260
| v5    |  2/20 +  6/200 | 0.130
| total | 14/20 + 42/200 | (91%)

The proba to have a 3rd round is 9%, that is 9/500 for each index

| value | proba 3 rounds            |
| v1    |  2/20 +  6/200 +  18/2000 | 0.1390
| v2    |  3/20 +  9/200 +  27/2000 | 0.2085
| v3    |  3/20 +  9/200 +  27/2000 | 0.2085
| v4    |  4/20 + 12/200 +  36/2000 | 0.2780
| v5    |  2/20 +  6/200 +  18/2000 | 0.1390
| total | 14/20 + 42/200 + 126/2000 | (97,3%)

So we see that the serie is converging to the correct probabilities. The numerators are multiple of the weight, so it's clear that the relative weight of each element is respected.

This is a sketch of an answer.

With weights only 1, we can maintain a random permutation of the inputs. Each time an element is inserted, put it at the end of the array, then pick a random position i in the array, and swap the last element with the element at position i. (It may well be a no-op if the random position turns out to be the last one.) When deleting, just delete the last element.

Assuming we can use a dynamic array with O(1) (worst case or amortized) insertion and deletion, this does both insertion and deletion in O(1).

With weights 1 and 2, the similar structure may be used. Perhaps each element of weight 2 should be put twice instead of once. Perhaps when an element of weight 2 is deleted, its other copy should also be deleted. So we should in fact store indices instead of the elements, and another array, locations, which stores and tracks the two indices for each element. The swaps should keep this locations array up-to-date.

Deleting an arbitrary element can be done in O(1) similarly to inserting: swap with the last one, delete the last one.