Изменения

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