Изменения

[[Файл:ListABCD.jpg|250px|thumb|right|Для такого списка команда операция <tex>\mathrm{order(D,B)}</tex> выдаст <tex>\mathrm{false}</tex>.]]'''List order maintance''' (русскрус. <i>поддержка поддержание порядка в списке</i>) {{---}} проблема поддержки поддержания списка со следующими операциями:

* <tex>\mathrm{order(p, q)}</tex> {{---}} командаоперация, возвращающая <tex>\mathrm{true}</tex> , если <tex>p</tex> в списке находится до <tex>q</tex> и <tex>\mathrm{false}</tex> иначе.

Существует реализация такой структуры, где все <tex>\mathrm{order(p, q)}</tex> выполняется за истинную <tex>O(1)</tex>, а операции выполняются добавления и удаления за амортизационную <tex>O(1)</tex>.Список с командой Проблема поддержания порядка используется в разных алгоритмах и структурахсписке возникает, к примеру, в при реализации полностью [[Персистентные структуры данных|полностью персистентного дерева поиска]].

== Алгоритм за O(logn) ===== Идея ===

Рассмотрим реализацию списка с командой порядкаВсе операции, где все операции выполняются за амортизационную кроме <tex>O(\log n)</tex>. Дадим каждому элементу списка метки длины <tex>u</tex> из битов. Пусть <tex>u:\dfracmathrm{n}{2}<2^u \leqslant 2n</tex>order(p, где <tex>n</tex> {{---q)}} количество элементов в списке. Если после добавления или удаления элементов <tex>u</tex> перестанет удовлетворять неравенству, пересчитаем все метки заново. Пересчет меток занимает амортизационно за <tex>O(1)</tex> по аналогии может выполнить обычный [[Список|двусвязный список]], но с саморасширяющимся массивомего помощью невозможно получить информацию о порядке объектов. Пусть метки идут по возрастанию Для реализации этой операции каждому узлу можно сопоставить некоторое число так, чтобы все числа строго возрастали от начала к концу списка. Опишем взаимодействие с Таким образом, эти числа, которые в дальнейшим будут называться <b>метками при выполнении операций:</b>, задают порядок на элементах списка.

* <b>операция порядка:</b> Ответить на запрос <tex>\mathrm{order(p,q)}</tex> можно сделать, просто сравнив метки за <tex>O(1)</tex> (так как они идут по возрастанию);* <b>удаление вершины:</b> для выполнения , просто сравнив метки <tex>\mathrm{remove(p)}</tex> просто удалим элемент и <tex>pq</tex> вместе с его меткой за . Добавление меток никак не влияет на реализацию операции <tex>O\mathrm{remove(1p)}</tex> , проверим, удовлетворяет ли <tex>u</tex> неравенству, если нет {{---}} пересчитаем;* <b>добавление вершины:</b> для . Однако реализацию <tex>\mathrm{insert(p,q)}</tex> существуют два возможных случаяпотребуется изменить:** при добавлении нового элемента <btex>есть свободная метка:q</btex> проверим, есть ли между элементом после узла <tex>rp</tex> и следующим за ним элементом свободная метка. Если есть, дадим узлу <tex>q</tex> любую свободную необходимо присвоить метку между ними, которая строго больше предыдущего элемента и строго меньше следующего. После этого опять проверим <tex>u</tex> на соответствие неравенству. [[Файл:UBitTreeListABCD.jpg|350px|thumb|right|Точка {{В какой---}} метка в листе используется.]]** <b>свободной то момент возникнет ситуация, что новой метки не найдётся, тогда метки нет:</b> В случаеможно перераспределить среди элементов списка так, если между чтобы для узла <tex>pq</tex> и следующим за ним элементом свободной метки нетнашлась метка. Далее будет рассмотрен алгоритм, нам придется пересчитать метки описанным ниже способомкоторый позволяет эффективно реализовать эту идею.

=== Алгоритм за O(logn) ======= Способ хранения меток ====Метки будут храниться в виде чисел в двоичной системе счисления. Требуется выбрать такую длину для меток, чтобы перераспределения не случались слишком часто. Если <tex>u</tex> {{---}} длина каждой метки, то для начала пусть <tex>u:n<2^u \leqslant 2n</tex>, где <tex>n</tex> {{---}} количество элементов в списке. Если после добавления элементов какому-то элементу не хватит метки, увеличим <tex>u</tex> на <tex>1<b/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</btex> будет несколько уточнено. Все метки хранятся будут храниться в [[Сверхбыстрый цифровой бор | цифровом боре]] высоты <tex>u</tex> (там хранятся представлены не только используемые метки, а вообще все возможные заданной длины). В узлах будем хранитьВведем некоторые обозначения:* <b>в листьях</b> будем хранить, используется ли уже эта метка. Пусть <tex>\mathrm{weight(x)}</tex> {{---}} это количество помеченных (используемых) листьев (меток) в поддереве узла <tex>x</tex>, а ;* <tex>\mathrm{size(x)}</tex> {{---}} это количество всех листьев в поддереве <tex>x</tex>;* <b>в нелистовых узлах</b> будем хранить, является ли узел переполненным. Для любой <tex>1<\alpha<2</tex> будем считать, что узел дерева переполнен, если <tex>\dfrac{\mathrm{weightheight(x)}}</tex> {\mathrm{size(x)---}}высота узла <tex>\dfrac{1}{\alpha^{\mathrm{height(x)}}}</tex>в цифровом боре. Стоит заметить, что все листья всегда непереполнены. В худшем случае Также в каждом узле дополнительно будет храниться: <tex> \dfrac* в листьях {\mathrm{weight(leave)---}}{\mathrm{size(leave)}} = 1 = \dfrac{1}{\alpha^{\mathrm{height(x)}}} = \dfrac{1}{\alpha^{0}}</tex>. Получается, что, чем выше, тем более разреженными должны быть поддеревья непереполненных узлов.используется ли уже эта метка;

<b>Докажем амортизационную стоимость операции добавления.</b>* С одной стороныПолучается, повторное перераспределение меток в поддереве узла <tex>x</tex> потребуется, когда сын этого узла снова переполнится. Если <tex>y</tex> {{---}} сын <tex>x</tex>, то он переполнится, когда что за <tex>\dfrac{\mathrm{weight(y)}}{2\mathrm{size(y)}}>\dfrac{1}{\alpha^{\mathrm{height(x) - 1}}}</tex>. Чтобы это произошло, операций перераспределения меток требуется, чтобы было сделано еще сделать <tex>\mathrm{size(y)} \cdot (\dfrac{1}{\alpha^{\mathrm{height(x) - 1}}} - \dfrac{1}{\alpha^{\mathrm{height(x)}}}) = \mathrm{size(y)} \cdot \dfrac{\alpha - 1}{\alpha^{\mathrm{height(x)}}}</tex> добавленийопераций добавления.* С другой стороныИспользуя [[Амортизационный анализ | метод предоплаты]], следующее переспределение меток произойдетвидим, когда что если за каждую операцию добавления брать <tex>\mathrm{weight(x)} = \dfrac{\mathrm{size(x)}}{\alpha^{\mathrm{height(x)}}} = \dfrac{2\mathrm{size(y)}}{\alpha^{\mathrm{height(x)}}-1} </tex>. Получаетсямонет, то за добавления накопится достаточное количество монет, что чтобы расплатиться за <tex>\dfrac{2\mathrm{size(y)}}{\alpha^{\mathrm{height(x)}}} </tex> операций следующую операцию перераспределения меток требуется сделать в узле <tex>\mathrm{size(y)}*\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) ===

Предыдущий алгоритм работает за логарифм из-за того, что слишком часто приходится делать перераспределение метокперераспределять метки. Используем <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>u\alpha</tex> зависит от выбранной сильно влияет на реализацию структуры, так как <tex>\alphau</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> памяти.

* [https://www.lektorium.tv/lecture/14321 Lectorium {{---}} лекция Лекция А.С. Станкевича]* [https://en.wikipedia.org/wiki/Order-maintenance_problem Wikipedia {{---}} order maintance problemOrder Maintance Problem]