The Alias method: O(n) in space and O(1) biased number generator

https://en.wikipedia.org/wiki/Alias_method

Mind was utterly blown when I first understood the way this works in my late teens.