Изменения

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