3622
правки
Изменения
Нет описания правки
Применим амортизационный анализ. Копим деньги на дешевых операциях — берем столько монет, какое расстояние до края. Скопим их достаточно, чтобы расплатиться за преобразование верхнего дерева. Получаем амортизированную оценку O(log(w)) и истинную - O(w).
Здесь не имеет смысла использовать сливаемые деревья поиска, так как после слияния/разделения все равно нужно можифицировать модифицировать верхний бор.
Получилась та же оценка на операции, что и у Ван Эмде Боаса, но структура данных занимает O(n) памяти.
