Сжатое многомерное дерево отрезков

Эта статья находится в разработке!

Определение:

Пусть дан [math]p[/math]-мерный массив, в котором требуется быстро получать информацию о выбранных [math]n[/math] элементах. Сжатым [math]p[/math]-мерным деревом отрезков называется модификация [math]p[/math]-мерного дерева отрезков, позволяющая сократить объем занимаемой им памяти до [math]O(n\,log^{p-1}\,n)[/math].

позволяющая для заданного множества из [math]n[/math] p-мерных точек за время [math]O(log^p\,n)[/math] отвечать на запрос количества точек, находящихся в p-мерном прямоугольнике [math]((x_1,x_2),...,(z_1,z_2))[/math]