528. Random Pick with Weight

class Solution:

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


        total = 0

        for i in w:
            total += i
            self.prefixSum.append(total)

        self.total = total



    def pickIndex(self) -> int:
        
        num = random.uniform(0, self.total)

        l, r = 0, len(self.prefixSum)

        while l < r:

            m = (l + r) // 2

            if self.prefixSum[m] < num:
                l = m + 1
            else:
                r = m

        return l