Fast sampling and update of weighted items? (data structure like red-black trees?)
drcode: First, put all items into an array, computing a number k for each item, where k=(sum of all weights above it).Then, just generate a random number 0<x<(sum of all weights).Finally, do a binary search on the array O(log(n)) comparing x to k....As for the "updating" step, you didn't define that very well or state whether you're interested in minimizing that as well- But given that the number of items may be as large as N it seems that a naive linear update would be the best you could achieve.