Fast Proportional Selection

Have you tried the Alias Method? https://en.wikipedia.org/wiki/Alias_method

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.

An algorithm that generates (an average of) O(n) random variates has time complexity at least O(n), not O(1).

Before optimizing proportional selection, make sure that proportional selection is what you want! For population-based search algorithms like GAs, tournament selection is a better choice in most cases. It also has the benefit of being O(1), albeit with a bigger constant time because you have select several individuals and then resolve the tournament.

What is this used for?