1632
правки
Изменения
м
позволяющая для заданного множества из <tex>n</tex> p-мерных точек за время <tex>O(log^p\,n)</tex> отвечать на запрос количества точек, находящихся в p-мерном прямоугольнике <tex>((x_1,x_2),...,(z_1,z_2))</tex>[[Категория: Дискретная математика и алгоритмы]][[Категория: Дерево отрезков]]
rollbackEdits.php mass rollback
{{В разработке}} {{ОпределениеЗадача
|definition=
Пусть дан имеется множество <tex>pA</tex>-мерный массив и множество , состоящее из <tex>n</tex> его элементов.'''<br>Сжатым взвешенных точек в <tex>p</tex>-мерным деревом отрезков''' называется модификация мерном пространстве. Необходимо быстро отвечать на запрос о суммарном весе точек, находящихся в <tex>p</tex>-мерного дерева отрезков, позволяющая сократить объем занимаемой им памяти до мерном прямоугольнике <tex>O(nx_a,x_b),(y_a,y_b),\dots,log^{p-1}\(z_a,nz_b)</tex>.
}}
Вообще говоря, с поставленной задачей справится и [[Многомерное дерево отрезков|обычное <tex>p</tex>-мерное дерево отрезков]]. Для этого достаточно на <tex>i</tex>-том уровне вложенности строить дерево отрезков по всевозможным <tex>i</tex>-тым координатам точек множества <tex>A</tex>, а при запросе использовать на каждом уровне бинарный поиск для установления желаемого подотрезка. Очевидно, запрос будет делаться за <tex>O(\log^p\,n)</tex> времени, а сама структура данных будет занимать <tex>O(n^p)</tex> памяти.
==Оптимизация==
Для уменьшения количества занимаемой памяти можно провести оптимизацию <tex>p</tex>-мерного дерева отрезков. Для начала, будем использовать дерево отрезков с сохранением всего подотрезка в каждой вершине. Другими словами, в каждой вершине дерева отрезков мы будем хранить не только какую-то сжатую информацию об этом подотрезке, но и все элементы множества <tex>A</tex>, лежащие в этом подотрезке. На первый взгляд, это только увеличит объем структуры, но не все так просто. При построении будем действовать следующим образом — каждый раз дерево отрезков внутри вершины будем строить не по всем элементам множества <tex>A</tex>, а только по сохраненному в этой вершине подотрезку. Действительно, незачем строить дерево по всем элементам, когда элементы вне подотрезка уже были «исключены» и заведомо лежат вне желаемого <tex>p</tex>-мерного прямоугольника. Такое «усеченное» многомерное дерево отрезков называется '''сжатым''' (англ. ''compressed'').
==Построение дерева==
Рассмотрим алгоритм построения сжатого дерева отрезков на примере множества <tex>A</tex>, состоящего из <tex>4</tex>-х взвешенных точек в <tex>2</tex>-мерном пространстве (плоскости):<br>
<tex>
p=2,~~n=4,~~A:
\begin{cases}
(1, 3), \mbox{weight}=7 \\
(2, 1), \mbox{weight}=1 \\
(3, 3), \mbox{weight}=8 \\
(4, 2), \mbox{weight}=5
\end{cases}
</tex>
* Cоставим массив из всех <tex>n</tex> элементов множества <tex>A</tex>, упорядочим его по первой координате, построим на нём дерево отрезков с сохранением подмассива в каждой вершине<br>[[Файл:tree_built.png]]
* Все подмассивы в вершинах получившегося дерева отрезков упорядочим по следующей координате<br>[[Файл:sorted_y.png]]
* Повторим построение дерева для каждого из них (координата последняя, поэтому в вершинах этих деревьев мы уже ничего строить не будем — подмассивы в каждой вершине можно не сохранять)<br>[[Файл:tree_completed.png]]
<br>
===Псевдокод===
'''buildSubarrayTree'''('''element[]''' array):
<font color=green>// построение одномерного дерева отрезков на массиве array с сохранением подмассива в каждой вершине </font>
'''buildNormalTree'''('''element[]''' array):
<font color=green> // построение обычного одномерного дерева отрезков на массиве array </font>
'''getInsideArray'''(vertex v):
<font color=green>// получение подмассива, сохраненного в вершине vertex </font>
'''buildCompressedTree'''('''element[]''' array, '''int''' coordinate = 1): <font color=green>// рекурсивная процедура построения сжатого дерева отрезков</font>
'''if''' coordinate < p
sort(array, coordinate) <font color=green>// сортировка массива по нужной координате </font>
segmentTree = buildSubarrayTree(array);
'''foreach''' v: vertex '''in''' segmentTree
buildCompressedTree(getInsideArray(v), coordinate + 1);
'''if''' coordinate == p
sort(array, coordinate)
buildNormalTree(array);
==Анализ полученной структуры==
Легко понять, что сжатое <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>.
==См. также==
* [[Дерево отрезков. Построение]]
* [[Многомерное дерево отрезков]]
==Источники информации==
* [http://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков]
* [http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2 Википедия — Дерево отрезков]
