Lessons from Weighted Pick

Three key points:

$1.$ Weighted sampling transforms into range lookup using prefix sums.

$2.$ Binary search on sorted prefix sums gives $O(\log n)$ lookup time per query.

$3.$ This pattern appears in load balancing, random sampling, and simulation systems.