Сжатое многомерное дерево отрезков — различия между версиями
| Строка 3: | Строка 3: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
| − | Пусть дан <tex>p</tex>-мерный массив, в котором требуется быстро получать информацию о выбранных <tex>n</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> | позволяющая для заданного множества из <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
Эта статья находится в разработке!
| Определение: |
| Пусть дан -мерный массив, в котором требуется быстро получать информацию о выбранных элементах. Сжатым -мерным деревом отрезков называется модификация -мерного дерева отрезков, позволяющая сократить объем занимаемой им памяти до . |
позволяющая для заданного множества из p-мерных точек за время отвечать на запрос количества точек, находящихся в p-мерном прямоугольнике
