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