Изменения

[[Файл: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>.Потребность Проблема поддержания порядка в списке с командой порядка возникает, к примеру, в при реализации [[Персистентные структуры данных|полностью персистентного дерева поиска]].

Все операции , кроме <tex>\mathrm{order(p,q)}</tex> , за <tex>O(1)</tex> может выполнить обычный [[Список|двусвязный список]]. Проблема возникает в тот момент, когда мы хотим но с его помощью невозможно получить порядок элементов, так как связный список не хранит информацию о нёмпорядке объектов. Пусть Для реализации этой операции каждому узлу сопоставлено можно сопоставить некоторое числотак, при этом чтобы все числа строго возрастают возрастали от начала списка к его концусписка. Таким образом, эти числа, которые в дальнейшим будут называться <b>метками</b>, задают порядок на элементах списка. И, зная ссылки  Ответить на два элемента запрос <tex>\mathrm{order(p,q)}</tex> и можно за <tex>qO(1)</tex>, можно за просто сравнив метки <tex>O(1)p</tex> ответить на запрос и <tex>\mathrm{order(p,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> нашлась метка. Теперь рассмотрим Далее будет рассмотрен алгоритм, который позволяет эффективно реализовать эту идею.

==== Способ хранения меток ====Метки будем хранить будут храниться в виде чисел в двоичной системе счисления. Посмотрим, какой длины должны быть меткиТребуется выбрать такую длину для меток, чтобы перераспределения не случались слишком часто. Если <tex>u</tex> {{---}} длина каждой метки, то для начала пусть <tex>u:\dfrac{n}{2}<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> (там представлены не только используемые метки, а вообще все возможные заданной длины). Введем некоторые обозначения:* <tex>\mathrm{weight(x)}</tex> {{---}} количество помеченных (используемых) листьев (меток) в поддереве узла <tex>x</tex>;* <tex>\mathrm{size(x)}</tex> {{---}} количество всех листьев в поддереве <tex>x</tex>;* <tex>\mathrm{height(x)}</tex> {{---}} высота узла <tex>x</tex> в цифровом боре. Также в каждом узле дополнительно будет храниться:* в листьях {{---}} используется ли уже эта метка;[[Файл:UBitTreeExample.jpg|350px|thumb|right|Пример цифрового бора для меток, где узел с крестиком {{---}} переполненный узел, а с галочкой {{---}} непереполненный для <tex>\alpha=1,5</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>\mathrm{insert(p, q)}</tex>, но метка, следующая за меткой <tex>q</tex> уже присвоена элементу <tex>z</tex>. Тогда будем подниматься вверх от метки <tex>z</tex> до тех пор, пока не будет найден первый непереполненный узел. Может случиться такое, что на всем пути до корня не встретится ни одного непереполненного узла. Чтобы этого избежать, уточним значение границы <tex>u</tex>позже. Как только будет найден первый непереполненный узел, переназначим метки в поддереве этого узла так, чтобы они находились друг от друга на одинаковых расстояниях (места точно хватит, так как <tex>\dfrac{\mathrm{weight(x)}}{\mathrm{size(x)}}\leqslant\dfrac{1}{\alpha^{\mathrm{height(x)}}}</tex>, если узел непереполненный). После этого между занятыми метками будет не меньше <tex>\alpha^{\mathrm{height(x)}}</tex> свободных меток. ==== Доказательство времени работы ====Рассмотрим, как часто происходит перераспределение меток: * Если в поддереве узла было проведено перераспределение меток, то повторное перераспределение меток в поддереве узла <tex>x</tex> потребуется, когда сын этого узла снова переполнится.Если <tex>y</tex> {{---}} сын <tex>x</tex>, то он переполнится, когда <tex>\dfrac{\mathrm{weight(y)}}{\mathrm{size(y)}}>\dfrac{1}{\alpha^{\mathrm{height(x) - 1}}}</tex>. Чтобы это произошло, требуется, чтобы было сделано еще добавлений:

<bcenter>Перераспределение меток.</b> Тогда, как только мы получаем команду вставить элемент, которому не хватает метки, мы поднимаемся вверх от метки элемента <tex>p</tex>, пока не найдем первый непереполненный узел. Может случиться такое, что на всем пути до корня мы не найдем ни одного непереполненного узла. Чтобы этого избежать, изменим требования к <tex>u</tex> позже. Как только мы нашли первый непереполненный узел, переназначим метки в его поддереве так, чтобы они находились друг от друга на одинаковых расстояниях (места точно хватит, так как <tex>\dfrac{\mathrm{weight(x)}}{\mathrm{size(x)}}\leqslant\dfrac{1}{\alpha^{\mathrm{height(x)}}}</tex>, если узел непереполненный). После этого плотность распределения всех занятых листьев составит примерно <tex>= \dfrac{12\mathrm{size(y)}}{\alpha^{\mathrm{height(x)}}}</tex>.</center>

<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>.

Предыдущий алгоритм работает за логарифм из-за того, что слишком часто приходится делать перераспределение метокперераспределять метки. Используем <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]