77
правок
Изменения
Нет описания правки
{{Определение
|definition=
Пусть дан <tex>p</tex>-мерный массив и имеется множество <tex>A</tex>, состоящее из <tex>n</tex> его элементов.'''<br>Сжатым взвешенных точек в <tex>p</tex>-мерным деревом отрезков''' называется более емкая по памяти модификация <tex>p</tex>-мерного дерева отрезков, позволяющая реализовывать моноидальные операции (нахождение количества элементов, минимального элементамерном пространстве. Необходимо быстро отвечать на запрос о суммарном весе точек, etc) над элементами множества <tex>A</tex>, принадлежащими находящихся в <tex>p</tex>-мерному подмассиву мерном прямоугольнике <tex>(x_a,x_b),(y_a,y_b),\,...\,,(z_a,z_b)</tex>.
}}
Важно понимать, что индексы p-мерного подмассива вполне могут быть заменены координатами в p-мерном вещественном пространстве. Тогда для определения нужного отрезка необходимо будет воспользоваться бинарным поиском. Например, сжатое дерево отрезков решает следующую задачу: заданы <tex>n</tex> точек на плоскости с координатами <tex>(x_i,y_i)</tex>, посчитать количество точек на прямоугольнике <tex>(x_a,x_b),(y_a,y_b)</tex>.
