Of the top of my head, here's how I would go about this. First, preprocess your data: 1) Normalize the weights 2) Sort the items in descending order by weight

Of the top of my head, here's how I would go about this. First, preprocess your data: 1) Normalize the weights 2) Sort the items in descending order by weight 3) Calculate, for each item, the sum of the weights of all prior items 4) Enter the items into a binary search tree. The key into this tree is the sum you calculated in step 3. You can use whichever data structure you want here... red-black or splay would probably be best, but it depends on your situation. Now your O(log n) lookup: 1) Generate a random variate in [0,1) 2) Search the binary tree for the item with the largest key that is <= the variate.