102
правки
Изменения
Нет описания правки
'''Дерево отрезков''' (англ. ''Segment tree'') {{---}} это структура данных, которая позволяет за асимптотику <tex>O(\log n)</tex> реализовать любые операции, определяемые на [[Моноид | моноиде]]. Например, следующего вида: нахождение суммы (задача RSQ), минимума или максимума (задача RMQ) элементов массива в заданном отрезке <tex>a[l],a[l+1],...\dots,a[r]</tex>.
При этом дополнительно возможно изменение элементов массива: как изменение значения одного элемента, так и [[Несогласованные поддеревья. Реализация массового обновления | изменение элементов на целом подотрезке массива]], например разрешается присвоить всем элементам <tex>a[l...\dots r]</tex> какое-либо значение, либо прибавить ко всем элементам массива какое-либо число. Структура занимает <tex>O(n)</tex> памяти, а ее построение требует <tex>O(n)</tex> времени.
==Структура==
Структура представляет собой дерево, листьями которого являются элементы исходного массива. Другие вершины этого дерева имеют по два ребенка и содержат результат операции от своих детей (например минимум или сумму). Таким образом, корень содержит результат искомой функции от всего массива <tex>[0...\dots n-1]</tex>, левый ребёнок корня содержит результат функции на <tex dpi=120>[0...\dots\frac{n}{2}]</tex>, а правый, соответственно результат на <tex dpi=120>[\frac{n}{2}+1...\dots n-1]</tex>. И так далее, продвигаясь вглубь дерева.
==Построение дерева==
Пусть исходный массив <tex>a</tex> состоит из <tex>n</tex> элементов. Для удобства построения увеличим длину массива <tex>a</tex> так, чтобы она равнялась ближайшей степени двойки, т.е. <tex>2^k</tex>, где <tex>2^k \geqslant n</tex>. Это сделано, для того чтобы не допустить обращение к несуществующим элементам массива при дальнейшем процессе построения. Пустые элементы необходимо заполнить нейтральными элементами моноида. Тогда для хранения дерева отрезков понадобится массив <tex>t</tex> из <tex>2^{k+1}</tex> элементов, поскольку в худшем случае количество вершин в дереве можно оценить суммой <tex>n+\frac{n}{2}+\frac{n}{4}...\dots +1 < 2n</tex>, где <tex>n=2^k</tex>. Таким образом, структура занимает линейную память.
Процесс построения дерева заключается в заполнении массива <tex>t</tex>. Заполним этот массив таким образом, чтобы <tex>i</tex>-й элемент являлся бы результатом некоторой бинарной операции <tex>\circ</tex> от элементов c номерами <tex>2i+1</tex> и <tex>2i+2</tex>, то есть родитель являлся результатом бинарной операции от своих сыновей. Один из вариантов — делать рекурсивно. Пусть у нас имеются исходный массив <tex>a</tex>, а также переменные <tex>tl</tex> и <tex>tr</tex>, обозначающие границы текущего полуинтервала <tex>[tl, tr)</tex>. Запускаем процедуру построения от корня дерева отрезков (<tex>i=0</tex>, <tex>tl=0</tex>, <tex>tr=n</tex>), а сама процедура построения, если её вызвали не от листа, вызывает себя от каждого из двух сыновей и суммирует вычисленные значения, а если её вызвали от листа — то просто записывает в себя значение этого элемента массива (Для этого у нас есть исходный массив <tex> a </tex>). Асимптотика построения дерева отрезков составит <tex>O(n)</tex>.
Реализация построения сверху:
'''function''' treeBuild(a[], i, tl, tr):
<font color="green">// Мы находимся в вершине с номером i, который отвечает за полуинтервал [tl, tr)</font>
'''if''' tl == tr
Реализация построения снизу:
'''function''' treeBuild(a[]):
'''for''' i = n - 1 .. 2 * n - 1
t[i] = a[i - n - 1]
Для построения персистентного дерева отрезков из <tex>n</tex> элементов необходимо пройтись по всему дереву, попутно создавая все необходимые вершины. В листах создавать вершину, хранящую соответствующее значение. Промежуточные же вершины строим от левого и правого сыновей
'''function''' treeBuild(a[], tl, tr):
'''if''' tl == tr
'''return''' Vertex(a[tl])
[[Файл:persist.png]]
Здесь изображено персистентное дерево отрезков с операцией минимум, в котором изначально было <tex>3</tex> вершиныэлемента. Сперва к нему была добавлена вершина со значением <tex>2</tex>, а потом изменена вершина со значением <tex>7</tex>. Цвет ребер и вершин соответствует времени их появления. Синий цвет элементов означает, что они были изначально, зеленый {{---}} что они появились после добавления, а оранжевый {{---}} что они появились после изменения элемента.
'''function''' update(v, tl, tr, pos, val): '''if''' tr - tl == tr1
'''return''' Vertex(val)
tm = (tl + tr) / 2
==См. также==
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%B7%D0%B0%D0%BF%D1%80%D0%BE%D1%81%D0%B0_%D0%B2_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B5_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2_%D1%81%D0%B2%D0%B5%D1%80%D1%85%D1%83 - Реализация запросов к дереву отрезков сверху]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%B7%D0%B0%D0%BF%D1%80%D0%BE%D1%81%D0%B0_%D0%B2_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B5_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2_%D1%81%D0%BD%D0%B8%D0%B7%D1%83 - Реализация запросов к дереву отрезков снизу]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%81%D0%BE%D0%B3%D0%BB%D0%B0%D1%81%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D1%8B%D0%B5_%D0%BF%D0%BE%D0%B4%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D1%8C%D1%8F._%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%BC%D0%B0%D1%81%D1%81%D0%BE%D0%B2%D0%BE%D0%B3%D0%BE_%D0%BE%D0%B1%D0%BD%D0%BE%D0%B2%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F - Реализация массового обновления]
==Ссылки==
* [http[wikipedia://rain.ifmo.ru/cat/view.php/vis/trees/segment:Дерево отрезков|Википедия {{--2006 - Визуализатор дерева }} Дерево отрезков]]
* [http[wikipedia://eSegment tree|Wikipedia {{-maxx.ru/algo/segment_tree - MAXimal :: algo :: Дерево отрезков-}} Segment tree]]
* [http[wikipedia://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 :Моноид|Википедия {{--- Дерево отрезков — Википедия}} Моноид]]
* [http://rain.ifmo.ru/cat/view.wikipediaphp/vis/trees/segment-2006 Визуализатор дерева отрезков] * [http://e-maxx.orgru/wikialgo/Моноид - Моноид — Википедияsegment_tree MAXimal :: algo :: Дерево отрезков]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Дерево отрезков]]
