Изменения
→Использование персистентных структур данных для решения геометрических задач=
Чтобы найти точку внутри полосы будем подставлять <tex>x</tex>-координату точки-запроса в линейные функции и найдем в двоичном дереве место, где находится точка, затем определим, в каком многоугольнике лежит точка-запрос.
Итого обрабатывается n событий, каждое за <tex>lognlog\ n</tex> и <tex>m</tex> запросов, также каждый за <tex>lognlog\ n</tex>. Общее время работы алгоритма <tex>nlognnlog\ n</tex> <tex>+mlogn</tex> <tex>mlog\ n</tex>.
При решении ''online''-задачи вместо обычного двоичного дерева нужно поддерживать частично персистентное дерево. Будем идти слева направо и поддерживать персистентное дерево поиска. Тогда для каждой полосы у нас будет своя версия дерева.
Пусть приходит ''online''-запрос. Двоичным поиском найдем, в какой полосе находится точка. Далее делаем запрос к версии дерева, соответствующей этой полосе и получаем ответ. Итого для решения задачи нужно <tex>lognlog\ n</tex> препроцессинга и <tex>lognlog\ n</tex> на запрос.
== См. также ==
