Локализация в ППЛГ методом полос (персистентные деревья) кратко

Привет, Вы узнаете о том , что такое Локализация в ППЛГ методом полос (персистентные деревья), Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое Локализация в ППЛГ методом полос (персистентные деревья) , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.

Постановка задачи

Дан ППЛГ и некая точка P. Нужно локализовать точку в ППЛГ (выяснить, над/под каким ребром ППЛГ расположена эта точка).

Решение

Суть

Проведем через каждую вершину вертикальную прямую. Получим полосы (slabs). Пусть каждой полосе соответствует точка, через которую проведен левый край полосы. Будем хранить отсортированный массив x -координат, тогда за O(logn) можно найти, в какой полосе лежит P .

Локация точки

В каждой полосе отрезки, составляющие ППЛГ, могут пересекаться только в концах, причем эти точки пересечения могут лежать только на прямых, ограничивающих полосы (по построению). Об этом говорит сайт https://intellect.icu . Получается, что внутри каждой полосы можно отсортировать отрезки, которые лежат в ней, например, снизу вверх. Тогда, найдя нужную полосу, можно быстро найти нужный отрезок.

Одномерная задача

Персистентные деревья

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

Один из способов сделать дерево частично персистентным — node-copying (или path-copying, в разных источниках по-разному). Храним массив корней дерева. Когда нам нужно изменить ноду, мы создаем в этом массиве новый корень, но его поля left и right совпадают с таковыми в предыдущем корне. Далее мы идем от корня к ноде, которую хотим изменить. Все вершины по пути мы «копируем» так же, как и корень, при этом у предка меняем соответствующий указатель на новый. После этого мы меняем нужную нам ноду. Таким образом, для такого дерева нам нужно O(nlogn) памяти.

Можно усовершенствовать этот способ. Теперь в каждой ноде будет храниться номер версии и поля для ленивого изменения дерева: фиксированное количество запасных указателей left и right и номера версий для них. Когда мы хотим изменить ноду, вместо копирования записываем изменения в запасные указатели, если они еще есть, иначе создаем новую ноду и соответственно исправляем ее предка. Для поиска по версиям используем бинпоиск. Этот способ называется limited node copying, для него нужно O(n) памяти, потому что амортизированно за один апдейт копируем O(1) нод.

Локализация в полосе

Воспользуемся сбалансированным частично персистентным деревом для хранения отрезков в полосах. Каждая полоса — это новая версия дерева.

Время и память

На запрос нужно O(logn) , на препроцессинг — O(nlogn) ; памяти нужно O(n) .

Вау!! 😲 Ты еще не читал? Это зря!

• плоский прямолинейный граф , пплг , рсдс ,

Исследование, описанное в статье про Локализация в ППЛГ методом полос (персистентные деревья), подчеркивает ее значимость в современном мире. Надеюсь, что теперь ты понял что такое Локализация в ППЛГ методом полос (персистентные деревья) и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов