Изменения

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