Изменения

Для уменьшения количества занимаемой памяти можно провести оптимизацию <tex>p</tex>-мерного дерева отрезков. Для начала, будем использовать дерево отрезков с сохранением всего подотрезка в каждой вершине. Другими словами, в каждой вершине дерева отрезков мы будем хранить не только какую-то сжатую информацию об этом подотрезке, но и все элементы множества <tex>A</tex>, лежащие в этом подотрезке. На первый взгляд, это только увеличит объем структуры, но не все так просто. При построении будем действовать следующим образом — каждый раз дерево отрезков внутри вершины будем строить не по всем элементам множества <tex>A</tex>, а только по сохраненному в этой вершине подотрезку. Действительно, незачем строить дерево по всем элементам, когда элементы вне подотрезка уже были "исключены" и заведомо лежат вне желаемого <tex>p</tex>-мерного прямоугольника. Такое "усеченное" многомерное дерево отрезков называется '''сжатым'''.

Рассмотрим алгоритм построения сжатого дерева отрезков на следующем примере:<br>[[Файл:set_a.png]]

}

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

==Источники==

[http://e-maxx.ru/algo/export_segment_tree Дерево отрезков на e-maxx.ru]