77
правок
Изменения
Нет описания правки
Пусть имеется множество <tex>A</tex>, состоящее из <tex>n</tex> взвешенных точек в <tex>p</tex>-мерном пространстве. Необходимо быстро отвечать на запрос о суммарном весе точек, находящихся в <tex>p</tex>-мерном прямоугольнике <tex>(x_a,x_b),(y_a,y_b),\,...\,,(z_a,z_b)</tex>
}}
Вообще говоря, с поставленной задачей справится и обычное <tex>p</tex>-мерное дерево отрезков. Для этого достаточно на <tex>i</tex>-той глубине вложенности строить дерево отрезков по всевозможным <tex>i</tex>-тым координатам точек множества <tex>A</tex>, а при запросе для определения искомого отрезка использовать бинарный поиск. Очевидно, асимптотики времени на запрос и размера структуры составят будет делаться за <tex>O(log^p\,n)</tex> и времени, а сама структура данных будет занимать <tex>O(n^p)</tex> соответственнопамяти.
==Структура==
