Weighted Random - Prefix Sum

Build a prefix sum array. If weights = [1, 3, 2], prefix = [1, 4, 6].

prefix[i] = sum of weights[0] through weights[i].

Total weight is prefix[-1] (last element). Generate a random number r in [0, total).