Изменения

[[Файл: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\mathrm{order(lognp,q)}</tex>. Дадим каждому элементу списка метки длины , за <tex>uO(1)</tex> из битов. Метки будем хранить в виде может выполнить обычный [[Сверхбыстрый цифровой бор Список| цифрового борадвусвязный список]]. Пусть <tex>u:\dfrac{n}{2}<2^u \leqslant 2n</tex>, где <tex>n</tex> {{---}} количество элементов в спискено с его помощью невозможно получить информацию о порядке объектов. Если после добавления или удаления элементов <tex>u</tex> перестанет удовлетворять неравенствуДля реализации этой операции каждому узлу можно сопоставить некоторое число так, пересчитаем чтобы все метки заново. Пересчет меток занимает амортизационно <tex>O(1)</tex> по аналогии с саморасширяющимся массивом. Пусть метки идут по возрастанию числа строго возрастали от начала к концу списка. Таким образом, эти числа, тогда операцию которые в дальнейшим будут называться <texb>\mathrm{order(p,q)}метками</texb> можно сделать, сравнив метки за <tex>O(1)</tex>. Теперь опишем взаимодействие с метками при выполнении других командзадают порядок на элементах списка.

* Для выполнения Ответить на запрос <tex>\mathrm{removeorder(p,q)}</tex> можно за <tex>O(1)</tex>, просто удалим элемент сравнив метки <tex>p</tex> вместе с его меткой, проверим, удовлетворяет ли и <tex>uq</tex> неравенству, если нет {{---}} пересчитаем. * Для Добавление меток никак не влияет на реализацию операции <tex>\mathrm{insertremove(p,q)}</tex> существуют два возможных случая:** Метка <tex>r</tex>: . Однако реализацию <tex>\mathrm{r.label}>\mathrm{insert(p.label,q)} + 1</tex>, где потребуется изменить: при добавлении нового элемента <tex>rq</tex> {{---}} следующий за после узла <tex>p</tex> элемент в списке. Тогда между метками <tex>p</tex> и <tex>r</tex> есть свободная метка, которую мы дадим узлу <tex>q:\mathrm{q.label} = \dfrac{\mathrm{p.label}+\mathrm{r.label}}{2}</tex>необходимо присвоить метку, которая строго больше предыдущего элемента и строго меньше следующего. После этого опять проверим <tex>u</tex> на соответствие неравенству. [[Файл:UBitTreeListABCD.jpg|350px|thumb|right|Точка {{В какой---}} метка в листе используется.]]** В случаето момент возникнет ситуация, что новой метки не найдётся, тогда метки можно перераспределить среди элементов списка так, если между метками <tex>p</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> (там хранятся представлены не только используемые метки, а вообще все возможные заданной длины). В листьях будем хранить, используется ли уже эта метка. Пусть Введем некоторые обозначения:* <tex>\mathrm{weight(x)}</tex> {{---}} это количество помеченных (используемых) листьев (меток) в поддереве узла <tex>x</tex>, а ;* <tex>\mathrm{size(x)}</tex> {{---}} это количество всех листьев в поддереве <tex>x</tex>. Для любой <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>. Получается, что, чем выше, тем более разреженными должны быть поддеревья непереполненных узлов.используется ли уже эта метка;

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

=== Алгоритм за O(1) ===

Улучшим время работы операции добавления до <tex>O(1)</tex>Предыдущий алгоритм работает за логарифм из-за того, что слишком часто приходится перераспределять метки. Для этого будем использовать Используем <tex>\mathrm{y}{-}\mathrm{fast}{-tree}\mathrm{trie}</tex> (улучшенный модифицированный цифровой бор). Внутри каждого кусочка будем тоже присваивать каждому элементу метку от <tex>0</tex> , чтобы улучшить время работы операции добавления до <tex>2^{2u-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}{-tree}\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 problem] [[Категория:Дискретная математика и алгоритмы]Order Maintance Problem]