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>.
