Изменения

Вообще говоря, с поставленной задачей справится и обычное <tex>p</tex>-мерное дерево отрезков. ОчевидноЕсли дерево строить по индексам массива, то запрос операции на <tex>p</tex>-мерном прямоугольнике c помощью такой структуры будет выполняться за <texmath>O(\frac{log^p\,nS}{S})</texmath>, а сама структура будет занимать или порядка <tex>\Omega(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>-мерного прямоугольника. Для этого будем использовать сохранение всего подмассива в каждой вершине дерева отрезков.