Изменения

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

Ответить на запрос <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> хватило хватит метки. Далее будет рассмотрен алгоритм, который позволяет эффективно реализовать эту идею.

Метки будем хранить будут храниться в виде чисел в двоичной системе счисления. Посмотрим, какой длины должны быть меткиТребуется выбрать такую длину для меток, чтобы перераспределения не случались слишком часто. Если <tex>u</tex> {{---}} длина каждой метки, то для начала пусть <tex>u:\dfrac{n}{2}<2^u \leqslant 2n</tex>, где <tex>n</tex> {{---}} количество элементов в списке. Если после добавления или удаления элементов <tex>u</tex> перестанет удовлетворять неравенству, пересчитаем все метки заново. Пересчет меток занимает амортизационно <tex>O(1)</tex> по аналогии с саморасширяющимся массивом. Позже, в доказательстве времени работы, мы несколько уточним значение <tex>u</tex>будет несколько уточнено.

Будем хранить все Все метки будут храниться в [[Сверхбыстрый цифровой бор | цифровом боре]] высоты <tex>u</tex> (там хранятся представлены не только используемые метки, а вообще все возможные заданной длины). А также будем хранитьТакже в каждом узле дополнительно будет храниться:* <b>в листьях</b> {{---}} используется ли уже эта метка. Пусть <tex>\mathrm{weight(x)}</tex> {{---}} это количество помеченных (используемых) листьев (меток) в поддереве <tex>x</tex>, а <tex>\mathrm{size(x)}</tex> {{---}} это количество всех листьев в поддереве <tex>x</tex>;[[Файл:UBitTreeExample.jpg|350px|thumb|right|Пример цифрового бора для меток, где узел с крестиком {{---}} переполненный узел, а с галочкой {{---}} непереполненный для <tex>\alpha=1,5</tex>.]]* <b>в нелистовых узлах</b> {{---}} является ли узел переполненным. Для  Переполненным является узел, для которого для любой <tex>1<\alpha<2</tex> будем считать, что узел дерева переполнен, если выполнено <tex>\dfrac{\mathrm{weight(x)}}{\mathrm{size(x)}}>\dfrac{1}{\alpha^{\mathrm{height(x)}}}</tex>, где <tex>\mathrm{weight(x)}</tex> {{---}} это количество помеченных (используемых) листьев (меток) в поддереве узла <tex>x</tex>, а <tex>\mathrm{size(x)}</tex> {{---}} это количество всех листьев в поддереве <tex>x</tex>. Стоит заметитьВ листьях мы не храним наличие переполненности, что так как все листья всегда непереполнены. В крайнем случае: <tex> \dfrac{\mathrm{weight(leave)}}{\mathrm{size(leave)}} = 1 = \dfrac{1}{\alpha^{\mathrm{height(x)}}} = \dfrac{1}{\alpha^{0}}</tex>. Получается, что, чем выше, тем более разреженными должны быть поддеревья непереполненных узлов.

ТогдаПерераспределение меток потребуется выполнить в случае, когда для нового элемента нет свободной метки. Ниже будет описан способ выполнения перераспределения меток: как только мы получаем команду требуется вставить элемент<tex>p</tex>, которому не хватает метки, мы поднимаемся будем подниматься вверх от метки элемента , следующего за <tex>pq</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>. Чтобы это произошло, требуется, чтобы было сделано еще <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)}}} </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>\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>.

* <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</tex> зависит от выбранной <tex>\alpha</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]