Изменения

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

Пусть дан набор многоугольников, они не пересекаются, но могут иметь общие вершины, суммарное число вершин — <tex>n</tex>.

Запрос: точка <tex>(x,y)</tex>. Вернуть нужно многоугольник, в котором она находится. Количество точек <tex>m</tex>.