Изменения

'''Дерево отрезков''' (англ. ''Segment tree'') {{---}} это структура данных, которая позволяет эффективно (за асимптотику <tex>O(\log n))</tex> реализовать любые операции, определяемые на множестве, на котором данная операция ассоциативна, и существует нейтральный элемент относительно этой операции следующего вида: нахождение суммы (задача RSQ), минимума или максимума (задача RMQ) элементов массива в заданном отрезке (<tex>aто есть на [[iМоноид | моноиде]]...j]</tex>Например, суммирование на множестве натуральных чисел, поиск минимума на любом числовом множестве, где перемножение матриц на множестве матриц размера <tex>iN*N</tex> , объединение множеств, поиск наибольшего общего делителя на множестве целых чисел и <tex>j</tex> поступают на вход алгоритма), при многочленов. При этом дополнительно возможно изменение элементов массива: как изменение значения одного элемента, так и [[Несогласованные поддеревья. Реализация массового обновления | изменение элементов на целом подотрезке массива (т.е. ]], например разрешается присвоить всем элементам <tex>a[i...jl \ldots r]</tex> какое-либо значение, либо прибавить ко всем элементам массива какое-либо число). Структура занимает <tex>O(n)</tex> памяти и выстраивается из массива за , а ее построение требует <tex>O(n)</tex>времени.

Структура представляет собой дерево, листьями которого являются элементы исходного массива. Другие вершины этого дерева имеют по <tex>2 ребёнка </tex> ребенка и содержат сумму или минимум/максимум результат операции от своих детей (в зависимости от поставленной задачинапример минимум или сумму). Таким образом, корень содержит результат искомой функции от всего массива <tex>[0...\ldots n-1]</tex>, левый ребёнок корня содержит результат функции на <texdpi=120>[0...\ldots\dfrac{n/}{2}]</tex>, а правый, соответственно результат на <texdpi=120>[\dfrac{n/}{2}+1...\ldots n-1]</tex>. И так далее, продвигаясь вглубь дерева.

[[Файл:Segment_tree.jpg|right|380px|thumb|Пример дерева отрезков для вычисления сумм]]Пусть исходный массив <tex>a</tex> состоит из <tex>n</tex> элементов. Для удобства построения увеличим длину массива <tex dpi>a</tex> так, чтобы она равнялась ближайшей степени двойки, т.е. <tex>2^k</tex>, где <tex>2^k \ge geqslant n</tex>. Это сделано, для того чтобы не допустить обращение к несуществующим элементам массива при дальнейшем процессе построения. Пустые элементы можно необходимо заполнить нулями или бесконечностями (за бесконечностью стоит понимать, например, число, больше которого в данных ничего не появится) в зависимости от поставленной задачинейтральными элементами моноида. Тогда для хранения дерева отрезков понадобится массив <tex>t</tex> из <tex>2^{k+1}</tex> элементов, поскольку в худшем случае количество вершин в дереве можно оценить суммой <tex>n+\dfrac{n/}{2}+\dfrac{n/}{4...} \ldots +1 < 2n</tex>, где <tex>n=2^k</tex>. Таким образом, структура занимает линейную память. Процесс построения дерева заключается в заполнении массива <tex>t</tex>. Заполним этот массив таким образом, чтобы <tex>i</tex>-й элемент являлся бы результатом некоторой бинарной операции (для каждой конкретной задачи своей) от элементов c номерами <tex>2i+1</tex> и <tex>2i+2</tex>, то есть родитель являлся результатом бинарной операции от своих сыновей (обозначим в коде эту операцию как "<tex> \circ </tex>"). Один из вариантов — делать рекурсивно. Пусть у нас имеются исходный массив <tex>a</tex>, а также переменные <tex>\mathtt{tl}</tex> и <tex>\mathtt{tr}</tex>, обозначающие границы текущего полуинтервала. Запускаем процедуру построения от корня дерева отрезков (<tex>i=0</tex>, <tex>\mathtt{tl}=0</tex>, <tex>\mathtt{tr}=n</tex>), а сама процедура построения, если её вызвали не от листа, вызывает себя от каждого из двух сыновей и суммирует вычисленные значения, а если её вызвали от листа — то просто записывает в себя значение этого элемента массива (Для этого у нас есть исходный массив <tex> a </tex>). Асимптотика построения дерева отрезков составит, таким образом, <tex>O(n)</tex>. Выделяют два основных способа построения дерева отрезков: построение снизу и построение сверху. При построении [[Реализация запроса в дереве отрезков снизу | снизу]] алгоритм поднимается от листьев к корню (Просто начинаем заполнять элементы массива <tex>t</tex> от большего индекса к меньшему, таким образом при заполнении элемента <tex> i </tex> его дети <tex>2i+1</tex> и <tex>2i+2</tex> уже будут заполнены, и мы с легкостью посчитаем бинарную операцию от них), а при построении [[Реализация запроса в дереве отрезков сверху | сверху]] спускается от корня к листьям. Особенные изменения появляются в реализации запросов к таким деревьям отрезков. [[Файл:Segment_tree.png|Пример дерева отрезков для минимума]] Реализация построения сверху:  '''function''' treeBuild('''T''' a[], '''int''' i, '''int''' tl, '''int''' tr): <font color=green>// мы находимся в вершине с номером i, который отвечает за полуинтервал [tl, tr) </font> '''if''' tr - tl == 1 t[i] = a[tl] '''else''' tm = (tl + tr) / 2 <font color=green>// середина отрезка</font> treeBuild(a, 2 * i + 1, tl, tm) treeBuild(a, 2 * i + 2, tm, tr) t[i] = t[2 * i + 1] <tex> \circ </tex> t[2 * i + 2] Реализация построения снизу:  '''function''' treeBuild('''T''' a[]): '''for''' i = 0 '''to''' n - 1 t[n - 1 + i] = a[i] '''for''' i = n - 2 '''downto''' 0 t[i] = t[2 * i + 1] <tex> \circ </tex> t[2 * i + 2] ==См. также==* [[Реализация запроса в дереве отрезков сверху]] *[[Реализация запроса в дереве отрезков снизу]]

Далее будем считать, что дерево выстраиваем для задачи вычисления суммы на отрезке. Для минимума и максимума операция построения проделывается аналогично*[[Несогласованные поддеревья.Реализация массового обновления]]

Процесс построения дерева заключается в заполнении массива <tex>t</tex>. Заполним этот массив таким образом, чтобы <tex>i</tex>-й элемент являлся бы суммой элемента c номером <tex>2i</tex> и элемента с номером <tex>2i+1</tex>, т.е. родитель являлся бы суммой своих сыновей. Лучше всего эту процедуру делать рекурсивно. Создадим функцию от исходного массива <tex>a</tex>, переменной <tex>i</tex>, обозначающей номер элемента в массиве <tex>t<==Источники информации== * [http:/tex>, а так же переменные <tex>tl</tex> и <tex>tr</tex>, обозначающие соответственно левую и правую границы текущего отрезкаhabrahabr. Запускаем процедуру построения от корня дерева отрезков (<tex>i=0<ru/tex>, <tex>tl=0<post/tex>, <tex>tr=n-1<115026/tex>), а сама процедура построения, если её вызвали не от листа, вызывает себя от каждого из двух сыновей и суммирует вычисленные значения, а если её вызвали от листа Хабрахабр — то просто записывает в себя значение этого элемента массива. Асимптотика построения дерева отрезков составит, таким образом, <tex>O(n)</tex>.Статья Максима Ахмедова]

Реализация* [http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006 Дискретная математика: Алгоритмы — Визуализатор дерева отрезков]

TreeBuild(a* [], i, tl, tr) if (tl = tr) t[i] = a[tl]; else tm = (tl + tr) http:// 2; e-maxx.ru/algo/середина отрезка TreeBuild(a, 2*i, tl, tm); TreeBuild(a, 2*i + 1, tm+1, tr); t[i] = t[2*i+1] + t[2*i+2segment_tree MAXimal :: algo :: Дерево отрезков];

==Ссылки==* [http://rainru.ifmo.ru/cat/viewwikipedia.php/visorg/treeswiki/segment-2006 - Визуализатор дерева %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://e-maxxru.wikipedia.ruorg/algowiki/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 - Дерево отрезков — Википедия]][[Категория: Структуры данных]]