Изменения

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