Weighted Pick - Implementation

Here's the complete solution:

class Solution
    prefix := array of size n
    total := 0

    function __init__(weights)
        n := length of weights
        for i from 0 to n - 1
            total := total + weights[i]
            prefix[i] := total

    function pickIndex()
        // Pick random number in [1, total]
        r := random integer in range [1, total]
        // Binary search for smallest i where prefix[i] >= r
        left := 0
        right := length of prefix - 1
        while left < right
            mid := left + (right - left) / 2
            if prefix[mid] < r then
                left := mid + 1
            else
                right := mid
        return left

Time: $O(n)$ for initialization (building prefix sum), $O(\log n)$ per pick (binary search). Space: $O(n)$ for the prefix sum array.