Изменения

==Решение==

===Суть===

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

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

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

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

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

*Sarnak, Tarjan "Planar Point Location Using Persistent Search Trees"

*de Berg и компания, Computational Geometry, третье издание, стр. 122-123