Random Pick with Weight

Problem Description

You are given a 0-indexed array of positive integers w where w[i] describes the weight of the i-th index. Your task is to implement a class WeightedRandomPicker that supports weighted random selection.

The probability of picking index i is proportional to w[i] / sum(w). In other words, indices with higher weights should be picked more frequently.

Class Interface

Implement the WeightedRandomPicker class:

• WeightedRandomPicker(int[] w) — Initializes the object with the given weight array w.
• int pickIndex() — Returns a randomly selected index in the range [0, w.length - 1]. The probability of picking index i is w[i] / sum(w).

Key Insight

Rather than storing weights directly, think about building a prefix sum array where each element represents the cumulative sum up to that index. Then generate a random number in the range [1, total_sum] and use binary search to find which index it falls into.

For example, if w = [1, 3, 2], the prefix sums are [1, 4, 6]. A random number in [1, 6]:

• Falls in [1, 1] → index 0 (probability 1/6)
• Falls in [2, 4] → index 1 (probability 3/6)
• Falls in [5, 6] → index 2 (probability 2/6)

Input/Output Format

Input: A list of operations where the first operation is always WeightedRandomPicker with weight array w, followed by one or more pickIndex calls.

Output: A list of results for each operation. The constructor returns null. Each pickIndex call returns a valid index.

Examples

Example 1

Input:  w = [1]
pickIndex() called 3 times
Output: [0, 0, 0]

With only one index, every pick must return 0.

Example 2

Input:  w = [1, 3]
pickIndex() called multiple times
Output: Each call returns 0 ~25% of the time and 1 ~75% of the time

Example 3

Input:  w = [3, 14, 1, 7]
pickIndex() called many times
Output: Index 1 appears most frequently (~56% of picks), index 0 ~12%, index 3 ~28%, index 2 ~4%

Approach Hints

1. Prefix Sums: Compute a prefix sum array from the weights. The last element equals the total weight sum.
2. Random Number: Generate a random integer in .