528. Random Pick with Weight

class Solution:
    def __init__(self, w: List[int]):
        """
        main idea:  presum + binary search 
        tc O(N) sc O(N)
        """
        self.psum = [0] * len(w)
        self.psum[0] = w[0]
        for i in range(1,len(w)):
            self.psum[i] = self.psum[i-1] + w[i] # can update directly from  array w 
        
    def pickIndex(self) -> int:
        """tc O(lgN)  sc O(1)
        """
        total = self.psum[-1]
        val = random.random() * total # val = random.randint(1,total) can be int or float 
        return bisect.bisect_left(self.psum,val)