Изменения

Вообще говоря, с поставленной задачей справится и обычное <tex>p</tex>-мерное дерево отрезков. Для этого достаточно на <tex>i</tex>-том уровне вложенности строить дерево отрезков по всевозможным <tex>i</tex>-тым координатам точек множества <tex>A</tex>, а при запросе использовать на каждом уровне бинарный поиск для установления желаемого подотрезка. Очевидно, запрос будет делаться за <tex>O(log^p\,n)</tex> времени, а сама структура данных будет занимать <tex>O(n^p)</tex> памяти.

Для уменьшения количества занимаемой памяти можно провести оптимизацию <tex>p</tex>-мерного дерева отрезков. Для начала, будем использовать дерево отрезков с сохранением всего подотрезка в каждой вершине. Другими словами, в каждой вершине дерева отрезков мы будем хранить не только какую-то сжатую информацию об этом подотрезке, но и все элементы множества <tex>A</tex>, лежащие в этом подотрезке. Казалось бы, это только увеличит объем структуры, но не все так просто. При построении будем действовать следующим образом — каждый раз дерево отрезков внутри вершины будем строить не по всем элементам множества <tex>A</tex>, а только по сохраненному в этой вершине подотрезку. Действительно, незачем строить дерево по всем элементам, когда элементы вне подотрезка уже были "исключены" и заведомо лежат вне желаемого <tex>p</tex>-мерного прямоугольника.