Случайный выбор элемента из взвешенного списка

У меня есть список из 100 000 объектов. Каждый элемент списка имеет связанный с ним «вес», который является положительным целым числом от 1 до N.

Как наиболее эффективно выбрать случайный элемент из списка? Я хочу, чтобы мое распределение случайно выбранных элементов было таким же, как и распределение весов в списке.

Например, если у меня есть список L = {1,1,2,5}, мне нужен 4-й элемент должен выбираться в среднем в 5/9 раз.

Предположим, что вставки и удаления являются обычными в этом списке, поэтому любой подход с использованием «таблиц целой площади» необходимо часто обновлять - надеясь, что найдется решение с O (1) требуется время выполнения и O (1) дополнительная память.