Изменения

'''Дерево отрезков''' (англ. ''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>P</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/ Хабрахабр — Статья Максима Ахмедова]

===Псевдокод===<code> addElement(Tree, ver, x) if Tree.isFullBinary(ver) Node tmpRoot = new Node(); roots* [Tree.countOfVersions++ + 1] = recAdd(tmpRoot, null, 0, 2 * Treehttp://rain.size(ver), x, Treeifmo.size(ver) + 1); else ru/cat/ k : 2 ^ (k - 1) <= Treeview.size(ver) < 2 ^ k roots[Tree.countOfVersions++ + 1] = recAdd(roots[ver], null, 0, 2 ^ k, x, Tree.size(ver) + 1); Node recAdd(node, parent, l, r, x, n) php/vis/trees/ Мы находимся в узле node, который отвечает за полуинтервал (l, rsegment-2006 Дискретная математика: Алгоритмы — Визуализатор дерева отрезков] if r - l == 1 return new Node(parent, x) m = (l + r) / 2; if node == null Node tmp = new Node(parent); node = tmp; else Node tmp = node.clone(); tmp.parent = parent; if n <= m tmp.L = recAdd(node.L, tmp, l, m, x, n); else tmp.R = recAdd(node.R, tmp, m, r, x, n); tmp.valueOfFunction = f(tmp.L, tmp.R); return tmp;

Node change(Tree, parent, node, l, r, i, x) * [http://изменить i-ый элемент на x if r e- l == 1 return new Node(x); else m = (l + r) / 2; Node tmp = node.clone(); tmp.parent = parent; if i <= m tmp.L = change(Tree, tmp, node.L, l, m, i, x); else tmp.R = change(Tree, tmp, node.R, m, r, i, x); tmpmaxx.valueOfFunction = f(tmp.L, tmp.R); if(node.parent == null) roots[Tree.countOfVersions++ + 1] = tmp; return tmp;<ru/code>Здесь функции <tex>recAdd()<algo/tex> и <tex>change()</tex> возвращает указатель на узел новой ветки.[[Файлsegment_tree MAXimal :: algo ::persist.png]Дерево отрезков]

==Ссылки==* [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/Моноид - Моноид — Википедия]