Leetcode 528. Random Pick with Weight

Given an array of positive weights, implement pickIndex() to return index i with probability w[i]/sum(w); the typical approach preprocessing prefix sums and using a random number plus binary search maps the random draw to the weighted bucket in O(log n) time after O(n) setup.