Solutions

1. Prefix Sum + Linear Search

class Solution:

    def __init__(self, w: List[int]):
        self.w = w
        self.total = sum(w)

    def pickIndex(self) -> int:
        target = self.total * random.random()
        curSum = 0
        for i in range(len(self.w)):
            curSum += self.w[i]
            if curSum > target:
                return i

Time & Space Complexity

Time complexity: $O(n)$ for initializing and $O(n)$ for each $pickIndex()$ function call.
Space complexity: $O(n)$

2. Prefix Sum + Binary Search

class Solution:

    def __init__(self, w: List[int]):
        self.prefix = [0]
        for wgt in w:
            self.prefix.append(self.prefix[-1] + wgt)

    def pickIndex(self) -> int:
        target = self.prefix[-1] * random.random()
        l, r = 1, len(self.prefix)
        while l < r:
            mid = (l + r) >> 1
            if self.prefix[mid] <= target:
                l = mid + 1
            else:
                r = mid
        return l - 1

Time & Space Complexity

Time complexity: $O(n)$ for initializing and $O(\log n)$ for each $pickIndex()$ function call.
Space complexity: $O(n)$