Изменения
→Структура
==Структура==
Вообще говоря, с поставленной задачей справится и обычное <tex>p</tex>-мерное дерево отрезков. Очевидно, запрос операции на <tex>p</tex>-мерном прямоугольнике c помощью такой структуры будет выполняться за <tex>O(log^p\,n)</tex>, а сама структура будет занимать порядка <tex>\Omega(S)</tex> памяти, где <tex>S</tex> — количество элементов в <tex>p</tex>-мерном массиве. Однако, можно провести следующую оптимизацию — каждый раз дерево отрезков внутри вершины будем строить только по тем элементам, которые встречаются в отрезке, за который отвечает эта вершина. Действительно, другие элементы уже были "исключены" и заведомо лежат вне желаемого <tex>p</tex>-мерного прямоугольника. Для этого будем использовать сохранение всего подмассива в каждой вершине дерева отрезков.==Построение дерева и запрос операции==Алгоритм построения такого "усеченного" дерева отрезков будет выглядеть следующим образом:<br>
* Cоставить массив из всех <tex>n</tex> элементов множества <tex>\Omega</tex>, упорядочить его по первой координате
* Построить на нём дерево отрезков (для удобства будем использовать сохранение всего с сохранением подмассива в каждой вершине дерева отрезков)
* Все подмассивы в вершинах получившегося дерева отрезков упорядочить по следующей координате, после чего повторить построение дерева для каждого из них
}
}
При такой оптимизации асимптотика размера структуры составит <tex>O(n\,log^{p-1}\,n)</tex>, а запрос будет аналогичен запросу в обычном <tex>p</tex>-мерном дереве отрезков за <tex>O(log^p\,n)</tex>. Но расплатой станет невозможность делать произвольный запрос модификации: в самом деле, если появится новый элемент, то это приведёт к тому, что мы должны будем в каком-либо дереве отрезков по второй или более координате добавить новый элемент в середину, что эффективно сделать невозможно.
