Этот вопрос является продолжением вопроса под ссылкой.
Мой вопрос заключается в выборке взвешенного случайного числа с дополнительным условием, что веса каждого элемента часто динамически изменяются.
РЕДАКТИРОВАТЬ Предположим, что нужно выбрать N элементов с разным весом.
Для статических весов метод псевдонима Уокера требует O (N) времени для настройки псевдонима, но стоимость выборки составляет O (1), поэтому он является одним из лучших для достижения моей цели.
И метод бинарного поиска требует также O (N) для создания кумулятивного массива, а стоимость выборки составляет log (N).
Однако в моем случае, поскольку веса часто меняются, временная сложность изменения весов также важна.
Поэтому я хочу знать, что существуют существующие библиотеки или алгоритмы с временной сложностью как для изменения структуры данных, так и для выборки менее O (N).
РЕДАКТИРОВАТЬ Пока я читаю комментарии, я понимаю, что мне нужно наложить дополнительные условия. На каждой фазе модификации изменяются только несколько чисел (в основном два) весов, также эти модификации не изменяют общую сумму весов (условие нормализации).
Если есть решение, я также хочу знать, можно ли его использовать, когда веса также являются действительными числами.
