Сжатое многомерное дерево отрезков — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 3: Строка 3:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Сжатым p-мерным деревом отрезков''' называется структура данных, позволяющая для заданного множества из <tex>n</tex> p-мерных точек за время <tex>O(log^p\,n)</tex> отвечать на запрос количества точек, находящихся в p-мерном прямоугольнике <tex>((x_1,x_2),...,(z_1,z_2))</tex>
+
Пусть дан <tex>p</tex>-мерный массив, в котором требуется быстро получать информацию о выбранных <tex>n</tex> элементах.'''<br>Сжатым <tex>p</tex>-мерным деревом отрезков''' называется модификация <tex>p</tex>-мерного дерева отрезков, позволяющая сократить объем занимаемой им памяти до <tex>O(n\,log^{p-1}\,n)</tex>.
 
}}
 
}}
 +
 +
позволяющая для заданного множества из <tex>n</tex> p-мерных точек за время <tex>O(log^p\,n)</tex> отвечать на запрос количества точек, находящихся в p-мерном прямоугольнике <tex>((x_1,x_2),...,(z_1,z_2))</tex>

Версия 07:44, 7 июня 2011

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


Определение:
Пусть дан [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]