419
правок
Изменения
Нет описания правки
== Простейший случай ==
Пусть дана прямая с точками на ней и отрезок. Точки даны в отсортированном порядке. Необходимо указать, какие из изначальных точек лежат на этом отрезке.
[[Файл:Line_with_dots_and_segment.png]] Данная задача решается с помощью функций из STL - upper_bound и lower_bound. upper_bound возвращает наименьшее значение больше данного, lower_bound - наибольшее значение меньше данного. Рассмотрим на примере: [[Файл:Upper_bound_and_lower_bound.png]]
Код реализации:
== Сбалансированное дерево поиска ==
Переходим к двумерному случаю. Пусть дано некоторое множество точек на плоскости. Нам необходимо ответить, какие именно из них лежат в некотором заданном прямоугольнике.
Для этого возьмем любое сбалансированное дерево поиска и слегка модернизируем его для более быстрой работы.
В каждом узле будем хранить точки, которые входят в его поддерево.
Теперь для ответа нам нужно спуститься отрезком по дереву и, если все поддерево лежит в отрезке, сразу выдавать его, если нет - спускаться дальше.
== Квадро дерево ==
== Инкрементальное квадро дерево ==
