Once you have the prefix sum array and a random number r, you need to find the smallest index i where prefix[i]≥r.
This is a classic binary search pattern. The prefix sum array is sorted, so binary search runs in O(logn) 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.