##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
Finding the target range
Once you have the prefix sum array and a random number , you need to find the smallest index where .
This is a classic binary search pattern. The prefix sum array is sorted, so binary search runs in time.
Why does this give correct probabilities? Because each index owns a range proportional to its weight, and you pick uniformly from all ranges combined.
