Викиконспекты - Вклад участника [ru]

Декартово дерево по неявному ключу

2012-04-04T17:38:06Z

Pashkal: Не трогайте цитату в начале!!!

{{Q|width=30%|Декартово дерево правит миром. За логарифм.|Неизвестный автор}}

==Постановка задачи==
Возьмем структуру данных '''[[Саморасширяющийся массив|вектор]]'''. В её стандартной реализации мы умеем добавить элемент в конец, узнать значение элемента, изменить элемент по номеру и удалить последний элемент. Расширим круг задач: теперь мы хотим добавлять элемент в любое место (с соответствующим изменением нумерации элементов) и удалять любой элемент (с тем же самым уточнением). Теперь нам нужно придумать структуру, называемую '''Декартово дерево по неявному ключу''', или же '''rope''' (''англ.'''веревка''''').

==Основная идея==
[[Файл:Tree_1.png|right|250px|thumb|Пример описанного дерева с демонстрацией определения ключа <tex>X</tex>]]
Напомним, '''[[Декартово дерево]]''' {{---}} это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу. Для решения задачи, поставленной в предыдущей главе, попробуем слегка модифицировать эту структуру. Если конкретнее, то оставим в нем только один ключ - ключ <tex>Y</tex>. Вместо второго ключа будем использовать следующую величину: '''количество элементов в нашей структуре, находящихся левее нашего элемента'''. Если проще, то будем считать ключом порядковый номер нашего элемента в дереве, уменьшенный на единицу.

Заметим, что при этом сохранится структура [[Дерево_поиска,_наивная_реализация|двоичного дерева поиска]] по этому ключу(т.е. наше модифицированное декартово дерево так и останется декартовым деревом). Однако, с этим подходом появляется проблема: наши операции добавления и удаления элемента могут поменять нумерацию, и при наивной реализации на изменение всех ключей потребуется <tex>O(n)</tex> времени, где <tex>n</tex> {{---}} количество элементов в дереве.

Как же нам быть? Основная идея заключается в том, что такой ключ <tex>X</tex> сам по себе нигде не хранится. Вместо него будем хранить вспомогательную величину <tex>C</tex>: '''количество вершин в поддереве нашей вершины'''(в поддерево включается и сама вершину). Обратим внимание, что все операции с обычным декартовым деревом делались сверху. Также заметим, что если по пути до некой вершины просуммируем все такие величины в левых поддеревьях, в которые мы не пошли, увеличенные на единицу, то придя в саму вершину и добавив к этой величине количество элементов в её левом поддереве, мы получим как раз ее ключ <tex>X</tex>.

==Операции, поддерживающие структуру декартова дерева==
Структура обычного декартова дерева поддерживается с помощью двух операций: '''split''' {{---}} разбиение одного декартова дерева на два таких, что в одном ключ <tex>X</tex> меньше, чем заданное значение, а в другом {{---}} больше, и '''merge''' {{---}} слияние двух деревьев, в одном из которых все ключи <tex>X</tex> меньше, чем во втором. С учетом отличий декартова дерева по неявному ключу от обычного, операции теперь будут описываться так: разбиение дерева на два так, что в левом окажется ровно <tex>t</tex> вершин, и слияние двух любых деревьев.

===Split===
Пусть процедура '''split''' запущена в корне дерева с требованием отрезать от дерева <tex>t</tex> вершин. Также известно, что в левом поддереве вершины находится <tex>l</tex> вершин, а в правом <tex>r</tex>. Рассмотрим сначала два тривиальных случая. Первый: <tex>l = t</tex>. В этом случае процедура '''split''' должна просто пометить, что у корня больше нет левого сына, и вернуть его бывшего левого сына в качестве левого ответа, а сам корень {{---}} в качестве правого. Второй случай (<tex>t = l + 1</tex>) рассматривается аналогично. Следующий случай не так тривиален: <tex>t < l</tex>. В этом случае нужно рекурсивно запустить процедуру '''split''' от левого сына с тем же параметром <tex>t</tex>, и левая часть сына станет левым ответом нашей процедуры, а правая часть станет левым сыном корня, после чего корень станет правым ответом. Случай <tex>t > l + 1</tex> рассматривается аналогично, с той лишь разницей, что от правого сына отрезается <tex>t - l - 1</tex> вершин.

===Merge===
Посмотрим любую из реализаций процедуры '''merge'''. Заметим, что в ней программа ни разу не обращается к ключу <tex>X</tex>. Поэтому реализация процедуры '''merge''' для декартова дерева по неявному ключу вообще не будет отличаться от реализации той же процедуры в обычном декартовом дереве.

===Поддержание корректности значений <tex>C</tex>===
Единственное действие, обеспечивающее корректность этих значений заключается в том, что после любого действия с детьми вершины нужно записать в ее поле <tex>C</tex> сумму этих значений в ее новых детях, увеличенную на единицу.

==Применение описанного дерева==
Что же мы получили? У нас есть структура, от которой можно отрезать слева кусок произвольной длины и слить два любых куска в один в нужном порядке. Теперь мы можем:
* вставить элемент в любое место (отрежем нужное количество слева, сольем левое дерево с деревом из одного добавленного элемента и результат {{---}} с правым деревом)
* переставить любой кусок массива куда угодно (сделаем нужные разрезы и слияния в правильном порядке)
* совершать групповые операции с элементами. Вспомним реализацию таких операций в дереве отрезков и поймем, что ничего не помешает нам сделать то же самое с описанным деревом. В групповые операции включается, естественно, и взятие функции от отрезка.
* сделав на одном исходном массиве два дерева из элементов разной четности, можно решить задачу про смену мест четных и нечетных на отрезке (одно из домашних заданий)
* повелевать миром

Алгоритм Бентли-Оттмана

2011-12-09T04:00:45Z

Pashkal: /* Сканирующая точка */

Алгоритм Бентли-Оттмана(англ. Bentley-Ottmann) - алгоритм, позволяющий по множеству отрезков на плоскости получить множество точек, в которых эти отрезки пересекаются, при этом для каждой точки алгоритм выдает множество отрезков, пересекающихся в ней.

==Постановка задачи==
[[Файл:pic1.jpg|right|560|thumb|Пример результата работы алгоритма]]
На плоскости лежит <tex>n</tex> отрезков, каждый из них задан координатами своих концов. Требуется по этим данным определить множество точек, в которых эти отрезки пересекаются. Однако, не всегда координаты точки можно абсолютно точно представить с помощью вещественных типов данных. Поэтому характеризовать каждую точку будем множеством отрезков, которые пересекаются в этой точке.

Для упрощения понимания введем два ограничения на входные данные:
* не существует вертикальных отрезков
* не существует пары отрезков, имеющих более одной общей точки
* никакие три отрезка не пересекаются в одной точке

Как обрабатывать эти случаи будет объяснено позднее.

==Алгоритм==

===Основная идея===
Алгоритм будет основан на идее сканирующей прямой. Опишем три типа событий, которые мы и будем обрабатывать:
* начался новый отрезок
* два отрезка пересеклись
* отрезок закончился

Сканирующая прямая будет расположена параллельно оси ординат, и двигаться вдоль оси абсцисс в сторону ее положительного направления. Учитывая введенные ограничения на входные данные, прямая никогда не будет проходить через два события одновременно.

===Статус===
[[Файл:pic2.jpg|right|560|thumb|Иллюстрация определения статуса]]
Назовем статусом множество, в которой содержатся все отрезки, пересекающие нашу сканирующую прямую. Важно, что эти отрезки должны быть упорядочены по возрастанию (или убыванию) координаты их пересечения с прямой. Заметим, что в процессе работы алгоритма отрезки могут добавляться в произвольные места этого упорядоченной множества, удаляться из произвольных мест или меняться местами друг с другом.

===Важная мысль===
Попробуем найти событие, которое случится раньше всех других, если наша прямая уже пересекает какие-то отрезки. Нам, в данный момент, интересен случай, когда это событие является пересечением отрезков. Важно, что в этом пересечении участвуют два отрезка, которые обязательно являются соседними в нашем статусе.

====Доказательство====
Предположим, что это не так. Значит, между этими двумя пересекающимися отрезками существует еще хотя бы один. Поскольку эти два отрезка пересекаются, то или третий пересекает перед их пересечением один из них, или пересекается с ними в той же точке. В любом случае, Важная мысль верна

===В итоге===
[[Файл:anim1.gif|right|560|thumb|Пример работы алгоритма]]
Изначально у нас есть только события вида "начался отрезок" и "закончился отрезок". События вида "пересекаются два отрезка" будут добавляться нами в множество еще не обработанных событий. Соответственно, алгоритм выглядит так: выбираем то событие из множества необработанных, у которого наименьшая координата <tex>X</tex>, обрабатываем, делаем так, пока множество необработанных событий непустое. Плюс, на протяжении всего алгоритма должен поддерживаться следующий инвариант: в множество необработанных событий уже добавлены все пересечения отрезков, которые в текущем статусе текущие.

===Обработка событий===
====Событие "начало отрезка"====
Находим в статусе два отрезка, между которыми будет находится тот, который начинается. После этого добавляем его в статус на это место и точки его пересечения с соседними добавляем в множество необработанных событий.

====Событие "конец отрезка"====
Находим в статусе отрезок, который заканчивается. Удаляем его оттуда, после чего в множество необработанных событий добавляем точку, в которой пересекаются отрезки, которые были соседями заканчивающегося в старом статусе. Это необходимо, потому что в новом статусе они станут соседними. Заметим, что добавляемое событие может уже находиться в множестве, но нас это совершенно не напрягает.

====Событие "пересечение отрезков"====
Находим в статусе два отрезка, которые пересекаются. Меняем их местами (это действительно происходит). После этого добавляем в множество пересечения двух новых пар соседей, которые появились после перестановки пересекшихся отрезков.

==Обработка "нехороших случаев"==
===Сканирующая точка===
Решим, для начала, вопрос с вертикальными отрезками. Важно, что заодно пропадет и проблема с обработкой событий, имеющих одинаковую координату по оси <tex>X</tex>.

[[Файл:anim2.gif|right|560|thumb|Сканирующая точка]]
Слегка поменяем нашу концепцию. Сканирующая прямая теперь становится не совсем прямой. Теперь у нас появляется, скорее, сканирующая точка. Суть изменения в следующем: в случае, если несколько событий попадают на одну вертикальную прямую, мы их обрабатываем в порядке возрастания координаты по оси <tex>X</tex>. Внимательный читатель сейчас, наверное, воскликнет: "А как же тогда наш статус? Ведь отрезки не могут пересекать точку!". Однако и это не является проблемой. Если отрезок, который лежит в статусе, не вертикален, то он сортируется по своей координате <tex>Y</tex>, в которой он пересекается с вертикальной прямой, проведенной через нашу точку (да, это бывшая сканирующая прямая). А вот если отрезок вертикален, то его параметром является как раз ордината "сканирующей точки". <s>Если внимательно подумать, то все будет корректно.</s>

===Несколько отрезков в одной точке===
====Первый метод решения проблемы====
У нас есть упорядоченное множество необработанных событий. Давайте перед добавлением события будем проверять, а нет ли его там. Если оно там уже есть, то события вида "в этой точке перечекаются отрезки <tex>A</tex> и <tex>B</tex>", превратится в событие вида "в этой точке пересекаются отрезки <tex>A</tex>, <tex>B</tex> и <tex>C</tex>". В процессе обработки этой точки порядок следования в статусе всех отрезков, пересекающихся в ней, просто инвертируется. Соответственно, проблема решилась.

====Второй метод решения проблемы====
На самом деле, посмотрим более внимательно, что произойдет в этой точке. Все пересечения всех пар обработаются. Всего таких пар <tex>k^2</tex>, где в точке пересекается <tex>k</tex> отрезков. Если в некой перестановке делается <tex>k^2</tex> элементарных транспозиций, и ни одна из них не повторяется, то перестановка становится инвертированной. Так что, даже если оставить все как есть, то все будет работать. <s>Такие дела.</s> Здесь тоже должна быть соответствующая анимашка.

===СНМ вместо отрезков===
'''Внимание! Этот раздел должен интересовать только <s>задротов</s> любознательных, так как он описывает разбор случая, который нам, по обещанию Ковалева, не встретится.'''
Нам остался последний сложный случай: наложение двух или более отрезков друг для друга. Давайте теперь вместо просто отрезков будем класть в СНМ следующее: множество отрезков, которые на данном этапе накладываются друг на друга. Понятно, что при добавлении нового отрезка он или создает свое множество, или добавляется в уже существующее. При удалении удаляется из множества, если оно осталось пустым - удаляется и само множество. А при пересечении с другим множеством попарно пересекаются все отрезки из двух множеств. При этом важно, что все отрезки, накладывающиеся друг на друга, должны занимать в статусе одну ячейку, т. е. являться одним множеством.

==Реализация алгоритма==
===Двоичное дерево поиска в качестве статуса===
Из определения статуса ясно, какую структуру удобно использовать в качестве статуса: двоичное дерево поиска. В нем удобно делать все необходимые операции, и выполняться они будут за <tex>O(log_2(n))</tex>.

===Реализация множества необработанных событий===
====Приоритетная очередь====
Опять же, эта идея возникает в процессе описания этого множества. При этом понятно, что точки сравниваются сначала по абсциссе, в случае равенства - по ординате.
====Двоичное дерево поиска====
В принципе, вполне себе вариант реализации упорядоченного множества. Но его стоит использовать только тогда, когда мы хотим рассматривать пересечение нескольких отрезков в одной точке в качестве отдельного случая, а не как несколько попарных пересечений. Заметим, что это существенно усложняет реализацию.

===Наконец, абсолютная точность===
Заметим, что мы не умеем получать абсолютно точные координаты пересечения двух отрезков. Однако, мы умеем представлять эти координаты в качестве суммы произведений нескольких чисел (просто пересечение прямых и раскрытие скобок в верхней части дроби). А сами координаты нам и не требуются, нам необходимо только уметь сравнивать эти координаты друг с другом. Сравнивать же эти суммы произведений с другими такими же суммами и с обычными числами (в обобщенном представлении тоже такими же суммами) мы тоже умеем. Победа!

Алгоритм Бентли-Оттмана

Задача о наибольшей общей подпоследовательности

2010-12-02T19:27:43Z

Pashkal: