Изменения

{{В разработке}} {{ОпределениеЗадача

Пусть дан <tex>p</tex>-мерный массив и имеется множество <tex>A</tex>, состоящее из <tex>n</tex> его элементов.'''<br>Сжатым взвешенных точек в <tex>p</tex>-мерным деревом отрезков''' называется модификация <tex>p</tex>-мерного дерева отрезков, позволяющая реализовывать моноидальные операции (нахождение количества элементовмерном пространстве. Необходимо быстро отвечать на запрос о суммарном весе точек, минимального элемента, etc) над элементами множества <tex>A</tex>, находящимися на находящихся в <tex>p</tex>-мерном прямоугольнике <tex>(x_a,x_b),(y_a,y_b),...\dots,(z_a,z_b)</tex>.

НапримерВообще говоря, сжатое с поставленной задачей справится и [[Многомерное дерево отрезков|обычное <tex>p</tex>-мерное дерево отрезков]]. Для этого достаточно на <tex>i</tex>-том уровне вложенности строить дерево отрезков решает следующую задачу: заданы по всевозможным <tex>ni</tex> -тым координатам точек множества <tex>A</tex>, а при запросе использовать на плоскости с координатами каждом уровне бинарный поиск для установления желаемого подотрезка. Очевидно, запрос будет делаться за <tex>O(x_i\log^p\,y_in)</tex>времени, посчитать количество точек на прямоугольнике а сама структура данных будет занимать <tex>O(x_an^p)</tex> памяти. ==Оптимизация==Для уменьшения количества занимаемой памяти можно провести оптимизацию <tex>p</tex>-мерного дерева отрезков. Для начала, будем использовать дерево отрезков с сохранением всего подотрезка в каждой вершине. Другими словами, в каждой вершине дерева отрезков мы будем хранить не только какую-то сжатую информацию об этом подотрезке, но и все элементы множества <tex>A</tex>, лежащие в этом подотрезке. На первый взгляд, это только увеличит объем структуры, но не все так просто. При построении будем действовать следующим образом — каждый раз дерево отрезков внутри вершины будем строить не по всем элементам множества <tex>A</tex>, а только по сохраненному в этой вершине подотрезку. Действительно,x_b)незачем строить дерево по всем элементам,когда элементы вне подотрезка уже были «исключены» и заведомо лежат вне желаемого <tex>p</tex>-мерного прямоугольника. Такое «усеченное» многомерное дерево отрезков называется '''сжатым''' (y_aангл. ''compressed''). ==Построение дерева==Рассмотрим алгоритм построения сжатого дерева отрезков на примере множества <tex>A</tex>,y_b)состоящего из <tex>4</tex>-х взвешенных точек в <tex>2</tex>.-мерном пространстве (плоскости):<br>

==Структура==Вообще говоря, с поставленной задачей справится и обычное <tex>p</tex>-мерное дерево отрезков. Очевидно=2,~~n=4, запрос операции на <tex>p</tex>-мерном прямоугольнике c помощью такой структуры будет выполняться за <tex>O~~A:\begin{cases} (log^p\1,n3)</tex>, а сама структура будет занимать порядка <tex>\Omegambox{weight}=7 \\(S2, 1)</tex> памяти, где <tex>S</tex> — количество элементов в <tex>p</tex>-мерном массиве. Однако\mbox{weight}=1 \\(3, можно провести следующую оптимизацию — каждый раз дерево отрезков внутри вершины будем строить только по тем элементам3), которые встречаются в отрезке\mbox{weight}=8 \\(4, за который отвечает эта вершина. Действительно2), другие элементы уже были "исключены" и заведомо лежат вне желаемого <tex>p\mbox{weight}=5\end{cases}</tex>-мерного прямоугольника. Для этого будем использовать сохранение всего подмассива в каждой вершине дерева отрезков.==Построение дерева и запрос операции==Алгоритм построения такого "усеченного" дерева отрезков будет выглядеть следующим образом:<br>* Cоставить Cоставим массив из всех <tex>n</tex> элементов множества <tex>A</tex>, упорядочить упорядочим его по первой координате* Построить , построим на нём дерево отрезков с сохранением подмассива в каждой вершине* Все подмассивы в вершинах получившегося дерева отрезков упорядочить по следующей координате, после чего повторить построение дерева для каждого из них<br>[[Файл:tree_built.png]]

* Все подмассивы в вершинах получившегося дерева отрезков упорядочим по следующей координате<br>[[Файл:sorted_y.png]] * Повторим построение дерева для каждого из них (координата последняя, поэтому в вершинах этих деревьев мы уже ничего строить не будем — подмассивы в каждой вершине можно не сохранять)<br>[[Файл:tree_completed.png]]<br>===Псевдокод:=== build_normal_tree'''buildSubarrayTree'''('''element[] ''' array) {: <font color=green>//построение одномерного дерева отрезков на массиве array с сохранением подмассива в каждой вершине }</font>

get_inside_array'''buildNormalTree'''(vertex'''element[]''' array) {: <font color=green> //получение подмассива, сохраненного в вершине vertex }построение обычного одномерного дерева отрезков на массиве array </font>

build_compressed_tree'''getInsideArray'''(vertex v): <font color=green>// получение подмассива, сохраненного в вершине vertex </font> '''buildCompressedTree'''('''element[] ''' array, '''int ''' coordinate = 01) { : <font color=green>//собственно, построение рекурсивная процедура построения сжатого дерева отрезков</font> '''if (''' coordinate < p) { sort(array, coordinate); <font color=green>//сортировка массива по нужной координате</font> segment_tree segmentTree = build_normal_treebuildSubarrayTree(array); for (each '''foreach''' v: vertex '''in segment_tree) ''' segmentTree { build_compressed_tree buildCompressedTree(inside_arraygetInsideArray(eachv), 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 Википедия — Дерево отрезков]

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