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

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

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

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


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