Изменения

Персистентные структуры данных используются при решении геометрических задач. Примером может служить [[Локализация в ППЛГ методом полос (персистентные деревья)|Point loctaion problem ]] — задача о местоположении точки. Задачи такого рода решаются в ''offline'' и ''online''. В ''offline''-задачах все запросы даны заранее и можно обрабатывать их одновременно. В ''online''-задачах следующий запрос можно узнать только после того, как найден ответ на предыдущий.

Сначала рассмотрим решение При решении ''offline''-задачи.Пусть дан набор множество данных многоугольников, они не пересекаются, но могут иметь общие вершины, суммарное число вершин — <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>log\ n</tex> будет своя версия дерева и <tex>m</tex> запросов, также каждый за <tex>log\ n</tex>сохранится возможность делать к ней запросы. Общее время работы алгоритма <tex>n</tex> <tex>log\ n</tex> <tex>+</tex> <tex>m</tex> <tex>log\ n</tex>. При решении Тогда ''onlinePoint loctaion problem''-задачи вместо обычного двоичного дерева нужно поддерживать частично персистентное дерево. Будем идти слева направо и поддерживать персистентное дерево поиска. Тогда для каждой полосы у нас будет своя версия дерева. Пусть приходит может быть решена в ''online''-запрос. Двоичным поиском найдем, в какой полосе находится точка. Далее делаем запрос к версии дерева, соответствующей этой полосе и получаем ответ. Итого для решения задачи нужно <tex>log\ n</tex> препроцессинга и <tex>log\ n</tex> на запрос.