Изменения
→Способ хранения меток
=== Идея ===
[[Файл:ListABCDwithMarks.jpg|250px|thumb|right|Пример расставления меток для списка, <tex>u=3</tex>.]]
Все операции , кроме <tex>\mathrm{order(p,q)}</tex> , за <tex>O(1)</tex> может выполнить обычный [[Список|двусвязный список]], но с его помощью невозможно получить информацию о порядке объектов. Чтобы реализовать эту операцию, Для реализации этой операции каждому узлу можно сопоставить некоторое число так, чтобы все числа строго возрастали от начала к концу списка. Таким образом, эти числа, которые в дальнейшим будут называться <b>метками</b>, задают порядок на элементах списка.
Ответить на запрос <tex>\mathrm{order(p,q)}</tex> можно за <tex>O(1)</tex>, просто сравнив метки <tex>p</tex> и <tex>q</tex>. Добавление меток никак не влияет на реализацию операции <tex>\mathrm{remove(p)}</tex>. Однако реализацию <tex>\mathrm{insert(p,q)}</tex> потребуется изменить: при добавлении нового элемента <tex>q</tex> после узла <tex>p</tex>, узлу <tex>q</tex> необходимо присвоить метку, которая строго больше предыдущего элемента и строго меньше следующего. В какой-то момент возникнет ситуация, что новой метки не найдётся, тогда метки можно перераспределить среди элементов списка так, чтобы для узла <tex>q</tex> нашлась метка. Далее будет рассмотрен алгоритм, который позволяет эффективно реализовать эту идею.
=== Алгоритм за O(logn) ===
==== Способ хранения меток ====
Метки будут храниться в виде чисел в двоичной системе счисления. Требуется выбрать такую длину для меток, чтобы перераспределения не случались слишком часто. Если <tex>u</tex> {{---}} длина каждой метки, то для начала пусть <tex>u:n<2^u \leqslant 2n</tex>, где <tex>n</tex> {{---}} количество элементов в списке. Если после добавления элементов какому-то элементу не хватит метки, увеличим <tex>u</tex> на <tex>1</tex> и пересчитаем все метки заново, распределив их равномерно. Заметим, что сразу после перераспределения меток, в среднем, между каждыми двумя элементами списка будет только одна свободная метка, так как при переходе к новому <tex>u</tex> количество меток будет примерно в два раза больше количества элементов списка. Если же после удаления элемента из списка <tex>2^u</tex> станет в <tex>4</tex> раза больше <tex>n</tex>, уменьшим <tex>u</tex> на <tex>1</tex>. Пересчет меток занимает амортизационно <tex>O(1)</tex> по аналогии с [[Динамический массив | саморасширяющимся массивом]]. Однако, очевидно, что в таком случае операция добавления за <tex>O(1)</tex> работать не будет, так как, если потребуется добавить между двумя элементами списка больше одного элемента, то новым элементам меток не хватит, и придется провести лишнее перераспределение меток, которое будет рассмотрено ниже. Позже, в доказательстве времени работы, значение <tex>u</tex> будет несколько уточнено.
Все метки будут храниться в [[Сверхбыстрый цифровой бор | цифровом боре]] высоты <tex>u</tex> (там представлены не только используемые метки, а вообще все возможные заданной длины). Введем некоторые обозначения:
* в нелистовых узлах {{---}} является ли узел переполненным.
<b>Переполненным</b> назовем узел, для которого для любой выбранного <tex>\alpha</tex> (<tex>1<\alpha<2</tex> ) выполнено <tex>\dfrac{\mathrm{weight(x)}}{\mathrm{size(x)}}>\dfrac{1}{\alpha^{\mathrm{height(x)}}}</tex>. В листьях не хранится наличие переполненности, так как все листья всегда непереполненыв листьях не может быть переполнения. В крайнем случае для листа: <tex> \dfrac{\mathrm{weight(x)}}{\mathrm{size(x)}} = 1 \ngtr 1 = \dfrac{1}{\alpha^{0}} = \dfrac{1}{\alpha^{\mathrm{height(x)}}} </tex>.
==== Перераспределение меток ====
Получается, что за <tex>\dfrac{2\mathrm{size(y)}}{\alpha^{\mathrm{height(x)}}} </tex> операций перераспределения меток требуется сделать <tex>\mathrm{size(y)} \cdot \dfrac{\alpha - 1}{\alpha^{\mathrm{height(x)}}}</tex> операций добавления. Используя [[Амортизационный анализ | метод предоплаты]], видновидим, что, если за каждую операцию добавления брать <tex>\dfrac{2}{\alpha-1}</tex> монет, то за добавления накопится достаточное количество монет, чтобы расплатиться за следующую операцию перераспределения в узле <tex>x</tex>.
Однако таким образом требуется платить за каждый уровень, а количество уровней (бит) равно <tex>u</tex>. Тогда амортизированная стоимость добавления составляет <tex>O(u)</tex>.
Для того, чтобы на пути к корню точно встретился непереполненный узел, требуется уточнить границы <tex>u</tex>: <tex>\dfrac{\mathrm{weight(root)}}{\mathrm{size(root)}} < \dfrac{1}{\alpha^{\mathrm{height(root)}}} \Rightarrow \dfrac{n}{2^u} < \dfrac{1}{\alpha ^u} \Rightarrow u \geqslant \log_{\frac{ 2}{\alpha}} n</tex>. Тогда операция добавления работает за <tex>O(\log n)</tex>.
=== Алгоритм за O(1) ===
[[Файл:GlobalandLocalLabelstoConst.jpg|350px|thumb|right|y-fast-tree для меток.]]
Предыдущий алгоритм работает за логарифм из-за того, что слишком часто приходится делать перераспределение метокперераспределять метки. Используем <tex>\mathrm{y}{-}\mathrm{fast}{-}\mathrm{trie}</tex> (модифицированный цифровой бор), чтобы улучшить время работы операции добавления до <tex>O(1)</tex>.
У каждого элемента списка будет две метки: глобальная и локальная. Глобальная задает блок, локальная {{---}} положение элемента внутри блока. Описание взаимодействия с метками:
* <b>локальные метки</b> внутри каждого блока будут присвоены каждому элементу от <tex>0</tex> до <tex>2^{2u-1}</tex> будут жадноприсвоены. Стоит заметить, что внутри блока никогда не будет проблемы, что кому-то не хватит метки или придется сделать перераспределение меток, так как, если каждый раз в качестве метки брать среднее значение, то для того, чтобы был конфликт из-за меток, нужно больше, чем <tex>2u</tex> ключей (противоречит условию);
* <b>глобальные метки</b> будут организованы в структуру, использовавшуюся в реализации операции за логарифмическое время. Глобальные метки для блоков придется менять, когда один из блоков переполнился. Тогда блок будет разделен на два, метка второму будет присвоена методом, описанным выше (поднимемся до первого непереполненного). Каждый блок будет иметь <tex>u</tex> занятых меток. Аналогично, когда в каком-то блок становится слишком мало ключей, он будет слит с соседним.
Внутри блоков присваиваются ключи за <tex>O(1)</tex>, а, аналогичный приведенному выше анализ показывает, что, чтобы потребовалось перераспределение к перераспределению глобальных меток, требуется приводит<tex>\Omega(u)</tex> изменений локальных меток. За эти изменения будет накоплено <tex>O(u)</tex> монет для изменения глобальных меток, тогда операция добавления работает за константное время.
== Использование памяти ==
Выбор <tex>\alpha</tex> сильно влияет на реализацию структуры, так как <tex>u</tex> зависит от выбранной <tex>\alpha</tex>. Увеличивая С увеличением <tex>\alpha</tex>, уменьшается стоимость операции добавления (количество монет, которые надо брать: <tex>\dfrac{2}{\alpha-1}</tex>), но увеличивается <tex>u</tex>, значит, требуется больше памяти, а, уменьшая <tex>\alpha</tex>, возникает получаем выигрыш в памяти, но проигрыш во времени операции добавления. Так как для реализации структуры используется <tex>\mathrm{y}{-}\mathrm{fast}{-}\mathrm{trie}</tex>, требуется <tex>O(n)</tex> памяти.
== Послесловие ==
