3622
правки
Изменения
м
→Алгоритм за O(1)
=== Алгоритм за O(1) ===
[[Файл:GlobalandLocalLabelstoConst.jpg|350px|thumb|right|y-fast-tree для меток.]]
Предыдущий алгоритм работает за логарифм из-за того, что слишком часто приходится делать перераспределение метокперераспределять метки. Используем <tex>\mathrm{y}{-}\mathrm{fast}{-}\mathrm{trie}</tex> (модифицированный цифровой бор), чтобы улучшить время работы операции добавления до <tex>O(1)</tex>.
У каждого элемента списка будет две метки: глобальная и локальная. Глобальная задает блок, локальная {{---}} положение элемента внутри блока. Описание взаимодействия с метками:
