Изменения
Нет описания правки
Оценим амортизационное время работы этого алгоритма. Введем потенциал, равный суммарному размеру нижних половин списков изменений во всех версиях. Когда мы раздваиваем узел, мы уменьшаем потенциал на половину размера списка изменений (в нашем примере это <tex>2P</tex>), затем мы переставляем <tex>P</tex> ссылок, потенциал увеличивается на <tex>P</tex>, значит амортизационное время работы - <tex>O(1)</tex>.
==Использование персистентных структур данных для решения геометрических задач===
Персистентные структуры данных используются при решении геометрических задач. Примером может служить Point loctaion problem – задача о местоположении точки. Задачи такого рода решаются в ''offline'' и ''online''. В ''offline''-задачах все запросы даны заранее и можно обрабатывать их одновременно. В ''online''-задачах следующий запрос можно узнать только после того, как найден ответ на предыдущий.
Сначала рассмотрим решение ''online''-задачи.
Пусть дан набор многоугольников, они не пересекаются, но могут иметь общие вершины, суммарное число вершин –<tex>n</tex>.
Запрос: точка<tex>(x,y)</tex>. Вернуть нужно многоугольник, в котором она находится. Количество точек <tex>m</tex>.
Через каждую вершину всех многоугольников проведем вертикальные прямые. Вся плоскость будет разбита на полосы. Внутри полос находится набор трапеций и треугольников, высеченных из многоугольников. Если посмотреть каждую из этих фигур слева направо, то это будет набор расширяющихся или сужающихся отрезков.
[[Файл:Локация точки.png]]
Используем технику, которая называется сканирующей прямой ''(scane line)''. Возьмем вертикальную прямую и направим ее из минус бесконечности в плюс бесконечность. Пусть она движется перпендикулярно себе по заданным нам многоугольникам. Порядок расположения отрезков, принадлежащих разным многоугольникам, задан однозначно. Возьмем точки, которые являются точками пересечения сканирующей прямой с границами многоугольников.
[[Файл:Одномерная задача.png]]
Сведем задачу к одномерной. Прямая проходит через точку <tex>A</tex>. Для того, чтобы найти в каком отрезке лежит эта точка, нужно точки-границы отрезков хранить отсортированными по возрастанию и найти между какими двумя точками лежит точка <tex>A</tex>. Это можно сделать бинпоиском. Если этот отрезок принадлежит какому-то из данных многоугольников, то значит и точка лежит внутри этого многоугольника.
Построим сбалансированное дерево поиска, в котором будем хранить точки, которые являются границами отрезков, но не в виде чисел, а как линейные функции вида <tex>y=kx+b</tex>. Для каждой вершины дерева ее ключ – это линейная функция.
При переходе из одной полосы в другую будем обрабатывать события. Это могут быть операции добавления, удаления, замены элементов в дерево.
Чтобы найти точку внутри полосы будем подставлять <tex>x</tex>-координату точки-запроса в линейные функции и найдем в двоичном дереве место, где находится точка, затем определим, в каком многоугольнике лежит точка-запрос.
Итого обрабатывается n событий, каждое за <tex>logn</tex> и <tex>m</tex> запросов, также каждый за <tex>logn</tex>. Общее время работы алгоритма <tex>nlogn+mlogn</tex>.
При решении ''online''-задачи вместо обычного двоичного дерева нужно поддерживать частично персистентное дерево. Будем идти слева направо и поддерживать персистентное дерево поиска. Тогда для каждой полосы у нас будет своя версия дерева.
Пусть приходит ''online''-запрос. Двоичным поиском найдем, в какой полосе находится точка. Далее делаем запрос к версии дерева, соответствующей этой полосе и получаем ответ. Итого для решения задачи нужно <tex>logn</tex> препроцессинга и <tex>logn</tex> на запрос.
== См. также ==
