note
abell
Say you have n values with probabilities d_1, ..., d_n.
Normalize your values so that all d_i's are at least 1. Then you can do with
O(sum(d_i)) storage and O(1) time. For each integer l less than sum(d_i)
there is at most one transition from one d_i to the next one between l and
l+1. For each l, just store either the outcome which covers all the l-th
unit interval or the two outcomes and the transition point.<br>
It's not the most elegant solution and in case you have very small values
you may think of some variation, but in your case it should work quite well.<br>
Best regards
158482
158482