Weighted Pick - Prefix Sum

The key insight: convert weights into cumulative ranges, then pick a random number in the total range.

For weights $[1, 3, 2]$, build prefix sums $[1, 4, 6]$. Index $0$ owns range $[1, 1]$, index $1$ owns range $[2, 4]$, index $2$ owns range $[5, 6]$. Pick a random number from $1$ to $6$, then find which range it falls into.

This transforms weighted sampling into a range lookup problem. Binary search finds the range in $O(\log n)$ time.