Изменения

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