Изменения

==Анализ полученной структуры==

Легко понять, что сжатое <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>.

==См. также==

* [[Дерево отрезков. Построение]]