<p>You are given a <strong>0-indexed</strong> array of positive integers <code>w</code> where <code>w[i]</code> describes the <strong>weight</strong> of the <code>i<sup>th</sup></code> index.</p>

<p>You need to implement the function <code>pickIndex()</code>, which <strong>randomly</strong> picks an index in the range <code>[0, w.length - 1]</code> (<strong>inclusive</strong>) and returns it. The <strong>probability</strong> of picking an index <code>i</code> is <code>w[i] / sum(w)</code>.</p>

<ul>
	<li>For example, if <code>w = [1, 3]</code>, the probability of picking index <code>0</code> is <code>1 / (1 + 3) = 0.25</code> (i.e., <code>25%</code>), and the probability of picking index <code>1</code> is <code>3 / (1 + 3) = 0.75</code> (i.e., <code>75%</code>).</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input</strong>
[&quot;Solution&quot;,&quot;pickIndex&quot;]
[[[1]],[]]
<strong>Output</strong>
[null,0]

<strong>Explanation</strong>
Solution solution = new Solution([1]);
solution.pickIndex(); // return 0. The only option is to return 0 since there is only one element in w.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input</strong>
[&quot;Solution&quot;,&quot;pickIndex&quot;,&quot;pickIndex&quot;,&quot;pickIndex&quot;,&quot;pickIndex&quot;,&quot;pickIndex&quot;]
[[[1,3]],[],[],[],[],[]]
<strong>Output</strong>
[null,1,1,1,1,0]

<strong>Explanation</strong>
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4.
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4.

Since this is a randomization problem, multiple answers are allowed.
All of the following outputs can be considered correct:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
and so on.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= w.length &lt;= 10<sup>4</sup></code></li>
	<li><code>1 &lt;= w[i] &lt;= 10<sup>5</sup></code></li>
	<li><code>pickIndex</code> will be called at most <code>10<sup>4</sup></code> times.</li>
</ul>

import random
class Solution:

    def __init__(self, w: List[int]):
        self.w = w
        self.cumm_sum = [sum(self.w[0:i[0]+1]) for i in enumerate(self.w)]
        self.total_weight = self.cumm_sum[-1]
        print(self.total_weight)

    def pickIndex(self) -> int:
        target = random.uniform(0, self.total_weight)
        index = self.bisect_left(0,len(self.cumm_sum), self.cumm_sum, target)
        return index

    def bisect_left(self, low, high, arr, target) -> int:
        """
        
        """
        if low <0:
            raise ValueError('lo must be non-negative')
        if high==None:
            high = len(arr)
        while low < high:
            mid = (low + high) //2
            if arr[mid]<target:
                low = mid+1
            else:
                high = mid
        return low

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

# import random

# class Solution:

#     def __init__(self, w):
#         self.prefix_sums = []
#         total = 0
#         for weight in w:
#             total += weight
#             self.prefix_sums.append(total)
#         self.total_weight = total

#     def bisect_left(self, a, x):
#         lo = 0
#         hi = len(a)
#         while lo < hi:
#             mid = (lo + hi) // 2
#             if a[mid] < x:
#                 lo = mid + 1
#             else:
#                 hi = mid
#         return lo

#     def pickIndex(self):
#         target = random.uniform(0, self.total_weight)
#         index = self.bisect_left(self.prefix_sums, target)
#         return index

21400