Изменения

Перейти к: навигация, поиск

Ортогональный поиск

15 байт добавлено, 16:38, 19 мая 2012
→‎Сбалансированное дерево поиска
# Для каждого из полученных поддеревьев обратимся к массиву содержащихся в нем точек и запустим от него приведенную выше функцию <tex>range{\_}search(y_{min}, y_{max})</tex>. Все полученные таким образом точки и будут составлять ответ.
Теперь для ответа нам нужно спуститься отрезком по дереву иКаждая из функций <tex>range{\_}search(y_{min}, если все поддерево лежит y_{max})</tex> будет работать в отрезкехудшем случае за <tex>O(\log n)</tex>, сразу выдавать его, если нет - спускаться дальшеотсюда получаем итоговое время выполнения запроса <tex>O(\log^2 n)</tex>.
== Квадро дерево ==
== Инкрементальное квадро дерево ==
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/22503»

Навигация