How to Design a Proportional Randomized Sampler?

Scenario

Randomized promotion engine must pick an item proportional to its score, but scores have no upper bound.

Question

Design a sampler pick() that returns an item with probability proportional to its (possibly very large) weight. Discuss memory and precision trade-offs when weights exceed 32-bit limits.

Hints

Prefix-sum array + binary search or alias table; rescale or use long/double for huge weights.

Weighted Pick by Rank Using Binary Search

You are given an array weights of n non-negative integers representing item weights, and an integer r such that 0 <= r < sum(weights). Implement weighted_pick(weights, r) that returns the smallest index i for which r < weights[0] + weights[1] + ... + weights[i]. This deterministically maps a uniform integer draw r in [0, sum(weights) - 1] to the item chosen proportionally to its weight. At least one weight must be positive. Use integer arithmetic to handle weights larger than 32-bit.

Constraints

• 1 <= n <= 2e5
• weights[i] are integers with 0 <= weights[i]
• At least one weights[i] > 0
• 0 <= r < sum(weights)
• sum(weights) <= 1e20 (weights may exceed 32-bit limits)
• Use integer arithmetic; avoid floating point precision loss

Examples

Example 1

Input: weights = [2,5,3], r = 6
Output: 1

Explanation: Prefix sums are [2,7,10]. Since 2 <= r=6 < 7, return index 1.

Example 2

Input: weights = [0,0,5], r = 3
Output: 2

Explanation: Only index 2 has positive weight; all r in [0,4] map to index 2.

Hints

1. Build a prefix-sum array of weights and binary search for the first prefix strictly greater than r.
2. Use 64-bit or arbitrary-precision integers; avoid floating point to prevent precision loss with huge weights.
3. Zero-weight items are never selected; using bisect-right over prefix sums naturally skips them.
4. For many repeated picks, precompute the prefix once or consider the alias method for O(1) sampling.

Approach

Compute the cumulative sums prefix[i] = sum(weights[0..i]). Given r in [0, total-1], the desired index i is the smallest index with prefix[i] > r. Using binary search (bisect_right) over the monotonic prefix array yields O(log n) lookup. This approach handles arbitrarily large weights without precision loss by staying in integer arithmetic. Zero-weight entries create repeated prefix values; bisect_right skips them automatically. For repeated queries, precompute the prefix once; alternatively, the alias method offers O(1) sampling at the cost of O(n) preprocessing and O(n) extra memory.

• Time complexity: O(n + log n) per call (O(n) to build prefix, O(log n) to search)
• Space complexity: O(n) extra space for prefix sums