Implement fast sampling for weighted k-sided die

You must sample from a categorical distribution over k outcomes with probabilities p1..pk (sum to 1) without using built-in categorical samplers. You have access only to a Uniform(0,1) RNG (or equivalently fair random bits). Design an algorithm with O(k) preprocessing time and O(1) sampling time per draw (e.g., Vose’s alias method). Provide: (a) clear build and sample pseudocode; (b) time and space complexity; (c) how you would handle extremely small probabilities and floating-point rounding so the resulting distribution is exactly normalized; (d) how to support incremental probability updates efficiently; (e) a statistical test plan (e.g., chi-square or KS on grouped bins) to validate the sampler’s correctness.