## Random Pick with Weight

• Time:Constructor: O(n), pickIndex(): O(\log n)
• Space:O(n)

## C++

``````class Solution {
public:
Solution(vector<int>& w) : prefix(w.size()) {
partial_sum(begin(w), end(w), begin(prefix));
}

int pickIndex() {
const int target = rand() % prefix.back();
int l = 0;
int r = prefix.size();

while (l < r) {
const int m = (l + r) / 2;
if (prefix[m] > target)
r = m;
else
l = m + 1;
}

return l;
}

private:
vector<int> prefix;
};
``````

## JAVA

``````class Solution {
public Solution(int[] w) {
prefix = w;
for (int i = 1; i < prefix.length; ++i)
prefix[i] += prefix[i - 1];
}

public int pickIndex() {
final int target = rand.nextInt(prefix[prefix.length - 1]);
int l = 0;
int r = prefix.length;

while (l < r) {
final int m = (l + r) / 2;
if (prefix[m] > target)
r = m;
else
l = m + 1;
}

return l;
}

private int[] prefix;
private Random rand = new Random();
}
``````

## Python

``````class Solution:
def __init__(self, w: List[int]):
self.prefix = list(accumulate(w))

def pickIndex(self) -> int:
target = randint(0, self.prefix[-1] - 1)
l = 0
r = len(self.prefix)

while l < r:
m = (l + r) // 2
if self.prefix[m] > target:
r = m
else:
l = m + 1

return l
``````