Design dynamic weighted random sampling with updates

Problem: Support weighted random sampling with insert/delete

Design a data structure that maintains a dynamic set of items, each with a positive integer weight, and supports:

1. insert(id, weight)
   • Adds a new item id with the given weight .
   • If id already exists, you may either reject or treat it as an update (state your choice).
2. delete(id)
   • Removes the item if it exists.
3. sample() -> id
   • Returns an id chosen randomly such that:

$P(id) = \frac{weight(id)}{\sum_j weight(j)}$

Requirements

• Target time complexity: O(log n) per operation.
• Must handle up to ~10^5 operations.
• Weights can be large (e.g., up to 10^9); total weight may exceed 32-bit.
• sample() should be unbiased given an ideal RNG.

Notes

• You may assume access to a function randInt(1, totalWeight) that returns a uniform integer in that range.
• Clearly define how you map item IDs to internal indices as the set changes over time.