Implement weighted random sampling with preprocessing

## Weighted Random Sampling (with performance follow-up) You are given an array of **positive** weights `w[0..n-1]`. Implement a data structure that supports: - `init(w)`: preprocess the weights. - `pick() -> int`: return an index `i` such that `P(pick() = i) = w[i] / sum(w)`. ### Requirements 1. Provide an approach where `pick()` runs in **O(log n)** time after preprocessing. 2. **Follow-up:** If `pick()` will be called **millions of times**, how would you redesign/precompute so that each `pick()` call is **O(1) expected time** (while keeping preprocessing reasonable)? ### Notes - Assume weights fit in 64-bit integer / double precision. - Clarify how you handle very large `sum(w)` and floating-point pitfalls if using doubles.