1
class Solution(object):
2
    def __init__(self, w):
3
        """
4
        :type w: List[int]
5
        """
6
        # Cumulative sum
7
        self.list = [0] * len(w)
8

9
        s = 0
10
        for i, n in enumerate(w):
11
            s += n
12
            self.list[i] = s
13

14
    def pickIndex(self):
15
        """
16
        :rtype: int
17
        """
18
        return bisect_left(self.list, random.randint(1, self.list[-1]))
19

20

21
# Your Solution object will be instantiated and called as such:
22
# obj = Solution(w)
23
# param_1 = obj.pickIndex()