Пусть имеется множество <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>
}}
Важно пониматьВообще говоря, что индексы p-мерного подмассива вполне могут быть заменены координатами в с поставленной задачей справится и обычное <tex>p</tex>-мерном вещественном пространстве. Тогда для определения нужного отрезка необходимо будет воспользоваться бинарным поиском. Например, сжатое мерное дерево отрезков решает следующую задачу: заданы . Для этого достаточно на <tex>ni</tex> точек на плоскости с координатами -той глубине вложенности строить дерево отрезков по всевозможным <tex>(x_i,y_i)i</tex>, посчитать количество -тым координатам точек на прямоугольнике множества <tex>(x_a,x_b),(y_a,y_b)A</tex>.
==Структура==
