Weighted Random Selection

Design a class WeightedPicker that, given an array of positive integers weights, supports picking a random index in [0, weights.length) where the probability of picking index i is proportional to weights[i]. Implement:

• WeightedPicker(weights: list[int]) — initializes the object with the given weights.
• pick() -> int — returns a random index using the weighting described above. Each call to pick() should run in O(log n) time.

Example

Input:
weights = [1, 3]
picker = WeightedPicker(weights)
picker.pick()  # returns 0 with probability 1/4, 1 with probability 3/4

Explanation: index 0 has weight 1 and index 1 has weight 3, so
out of every 4 picks, roughly 1 should land on index 0 and 3
should land on index 1.

Constraints

• 1 <= weights.length <= 10^4
• 1 <= weights[i] <= 10^5
• pick() is called at most 10^4 times.