528

class Solution {
public:
    vector<int> prefixSum;
    Solution(vector<int>& w) {
        prefixSum.assign(w.size(), 0);
        for(int i=0; i<w.size(); i++){
            prefixSum[i] = w[i] + ((i>0) ? prefixSum[i-1] : 0);
        }
    }

    int pickIndex() {
        float randNum = float(rand()) / RAND_MAX;
        float target = randNum * prefixSum.back();
        return upper_bound(prefixSum.begin(), prefixSum.end(), target)-prefixSum.begin();
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(w);
 * int param_1 = obj->pickIndex();
 */