Изменения

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

Пусть исходный массив <tex>a</tex> состоит из <tex>n</tex> элементов. Для удобства построения увеличим длину массива <tex>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|Пример дерева отрезков для максимумаминимума]]

TreeBuild'''function''' treeBuild('''T''' a[], '''int''' i, '''int''' tl, '''int''' tr): <font color=green>// Мы мы находимся в элементе вершине с номером i, который отвечает за полуинтервал [tl, tr)</font> '''if (tl = tr) return; if (''' tr - tl == 1) t[i] = a[tl]; '''else''' tm = (tl + tr) / 2; <font color=green>//середина отрезка</font> TreeBuild treeBuild(a, 2 * i + 1, tl, tm); TreeBuild treeBuild(a, 2 * i + 2, tm, tr); t[i] = f(t[2 * i + 1], <tex> \circ </tex> t[2 * i + 2]);

TreeBuild'''function''' treeBuild('''T''' a[]): '''for ''' i = 0 '''to''' n - 1 .. 2 * t[n - 1 t[+ i] = a[i - n - 1] '''for ''' i = n - 2 .. '''downto''' 0 t[i] = f(t[2 * i + 1], <tex> \circ </tex> t[2 * i + 2])

==Персистентное дерево отрезковСм. также=={{Определение|definition='''Персистентной''' (англ. ''Persistent'') называется такая структура данных, которая хранит все свои промежуточные версии.}}{{Определение|definition='''Полностью персистентной''' (англ. ''Fully persistent'') называется такая персистентная структура данных, * [[Реализация запроса в которой разрешено изменять любую её версию и делать запросы к любой её версии.}}На основе дерева дереве отрезков можно построить полностью персистентную структуру данных.сверху]]

===Структура дерева===Для реализации персистентного дерева *[[Реализация запроса в дереве отрезков удобно несколько изменить структуру дерева. Для этого будем использовать явные указатели <tex>L</tex> и <tex>R</tex> для дочерних элементов. Кроме того, заведем массив <tex>roots[снизу]</tex>, в котором <tex>roots[i]</tex> указывает на корень дерева отрезков версии <tex>i</tex>

===Построение===Для построения персистентного дерева отрезков из <tex>n</tex> элементов необходимо применить <tex>n</tex> раз операцию добавления элемента к последней версии дерева*[[Несогласованные поддеревья. Для того, чтобы добавить новый элемент к <tex>k</tex>-ой версии дерева, необходимо проверить, является ли оно полным бинарным. Если да, то создадим новый корень, левым сыном сделаем <tex>roots[kРеализация массового обновления]]</tex>. Иначе, сделаем копию корня исходной версии. Добавим корень в конец массива корней. Далее, спускаясь от корня к первому свободному листу, будем создавать несуществующие узлы и клонировать существующие. После этого в новой ветке необходимо обновить значение функции и некоторые указатели дочерних элементов. Поэтому, возвращаясь из рекурсии, будем менять один указатель на только что созданную или скопированную вершину, а также обновим значение функции, для которой строилось дерево. После этой операции в дереве появится новая версия, содержащая вставленный элемент.

===Изменение элемента=Источники информации==Для того, чтобы изменить элемент в персистентном дереве отрезков, необходимо сделать следующие действия* [http: спустимся в дереве от корня нужной версии до требуемого элемента, скопируем его, изменим значение, и, поднимаясь по дереву, будем клонировать узлы. При этом необходимо менять указатель на одного из детей на узел, созданный при предыдущем клонировании. После копирования корня, добавим новый корень в конец массива корней//habrahabr.ru/post/115026/ Хабрахабр — Статья Максима Ахмедова]

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

Здесь изображено персистентное дерево отрезков с операцией минимум, в котором изначально было 3 вершины. Сперва к нему была добавлена вершина со значением 2, а потом изменена вершина со значением 7. Цвет ребер и вершин соответствует времени их появления. Синий цвет элементов означает, что они были изначально, зеленый * [http://e- что они появились после добавления, а оранжевый - что они появились после изменения элементаmaxx.ru/algo/segment_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-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 Моноид - Дерево отрезков Википедия — Википедия] [http://ru.wikipedia.org/wiki/Моноид - Моноид — Википедия]