##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
Converting weights to ranges
The key insight: convert weights into cumulative ranges, then pick a random number in the total range.
For weights , build prefix sums . Index owns range , index owns range , index owns range . Pick a random number from to , then find which range it falls into.
This transforms weighted sampling into a range lookup problem. Binary search finds the range in time.
