You can actually do adjustable weight sampling in logarithmic time using a modification of the binary search approach, which is likely superior in a lot of case

You can actually do adjustable weight sampling in logarithmic time using a modification of the binary search approach, which is likely superior in a lot of cases. The trick is to keep a dense binary tree (arbitrary order--you can use the standard array mapping), where each leaf has one of your w_i and each internal node is the sum of its two children (and therefore equals the sum of all leaves in its subtree.) To update one weight, you just walk up the tree. To sample, you walk down the tree making a weighted decision at each point. This allows log n time update and sampling. It can be quite fast in practice, though the alias method is faster if you don't need adjustable weights. There are all sorts of other issues with RNG generation of doubles that affect these cases, though - I need to write a longer post about what I've done here.