Эффективный алгоритм случайной выборки из дистрибутива при разрешении обновлений?

Это вопрос, который мне задали некоторое время назад на собеседовании, я не смог найти ответа. для.

Для некоторых выборок S1, S2, ... Sn и их распределений вероятностей (или весов, как бы это ни называлось) P1, P2, .. Pn алгоритм проектирования, который случайным образом выбирает выборку с учетом ее вероятности.я пришел к следующему решению:

1. Построить совокупный массив весов Ci, например

   C0 = 0; Ci = C [i-1] + Pi.

одновременно вычисляют T = P1 + P2 + ... Pn. Это занимает O (n) раз

2. Сгенерировать равномерно случайное число R = T * random [0..1]
3. Используя алгоритм двоичного поиска, верните наименьшее i такое Ci> = R. результат - Si. Это занимает O (logN) времени.

Теперь актуальный вопрос: Предположим, я хочу изменить один из начальных весов Pj. как это сделать лучше, чем за O (n) время? другие структуры данных приемлемы, но алгоритм случайной выборки не должен быть хуже, чем O (logN).