Изменения

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