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

Материал из Викиконспекты
Перейти к: навигация, поиск
Эта статья находится в разработке!


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