Weighted Random Sampling by Index

Imagine an array weights of positive integers. For each position i, let total[i] be the sum of weights[0] through weights[i]. These cumulative totals split the nonnegative integers into disjoint half-open intervals: index 0 owns [0, total[0]), and for each i > 0, index i owns [total[i - 1], total[i]). A lookup receives an integer target in the range 0 target. Build the cumulative totals once in O(n) time. Each lookup should then run in O(log n) time. Example 1: Explanation:…