Random pick with weight

Given positive weights, implement pick() that returns index i with probability w[i] / sum(w). Build prefix sums once, then binary search a random number into them. One version gives cities with their populations and asks for a random city chosen in proportion to its population.