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