Изменения

==Построение дерева и запрос операции==

* Cоставить массив из всех <tex>n</tex> элементов множества <tex>A</tex>, упорядочить его по первой координате

* Построить на нём дерево отрезков с сохранением подмассива в каждой вершине

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

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

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