Random Pick with Weight

Problem

You are given an array w of positive integers where w[i] is the weight of index i. Design a class with a constructor that takes w and a method pickIndex() that returns an index in [0, len(w) - 1] at random, such that index i is chosen with probability w[i] / sum(w). pickIndex will be called many times, so it should be fast.

• The weight array is non-empty and has at most 50,000 entries.
• Every weight is a positive integer (strictly increasing prefix sums depend on this); weights can be as large as a million.
• Expect tens of thousands of pickIndex calls on one instance.

Examples

• w = [6] → pickIndex() always returns 0.
• w = [3, 1] → returns 0 with probability 3/4 and 1 with probability 1/4.
• w = [4, 1, 5] → returns 0, 1, 2 with probabilities 0.4, 0.1, 0.5 respectively.

Hints

1. Imagine laying the weights end to end as segments on a number line from 0 to the total. Throwing a dart uniformly at the line lands in segment i with probability proportional to w[i].
2. The right endpoints of those segments form a sorted array. Given the dart's position, how do you find which segment it hit?
3. Build a prefix-sum array of the weights; draw a uniform number in (0, total]; binary search for the first prefix that is at least the draw.