Background

What is your motivation?
The current WeightedIndex is pretty good. Lookups perform very well. And while it's possible to do updates, they are potentially slow as the (average) complexity is O(n). For matchmaking systems where updates are about as frequent as samples, this may be better served by an underlying datastructure which offers quick updates.

What type of application is this? (E.g. cryptography, game, numerical simulation)
Real-time matchmaking

Feature request

If I'm not mistaken, balanced tree structures like AVL trees or red-black trees enable O(log(n)) operations (search/ sample, update, insert, delete). The constant coefficient will obviously be worse than an implementation using a vector, but for large n, it should pay off.

Is this something that could have a place in rand? I'd be willing to take a shot at it if so.