Weighted Pick - Binary Search

Once you have the prefix sum array and a random number $r$, you need to find the smallest index $i$ where $prefix[i] \geq r$.

This is a classic binary search pattern. The prefix sum array is sorted, so binary search runs in $O(\log n)$ 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.