Дерево отрезков. Построение — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Псевдокод)
(Ошибка описания картинки)
(не показано 48 промежуточных версий 11 участников)
Строка 1: Строка 1:
'''Дерево отрезков''' {{---}} это структура данных, которая позволяет за асимптотику <tex>O(\log n)</tex> реализовать любые операции, определяемые на [[Моноид | моноиде]]. Например, следующего вида: нахождение суммы (задача RSQ), минимума или максимума (задача RMQ) элементов массива в заданном отрезке (<tex>a[i...j]</tex>, где <tex>i</tex> и <tex>j</tex> поступают на вход алгоритма)
+
'''Дерево отрезков''' (англ. ''Segment tree'') {{---}} это структура данных, которая позволяет за асимптотику <tex>O(\log n)</tex> реализовать любые операции, определяемые на множестве, на котором данная операция ассоциативна, и существует нейтральный элемент относительно этой операции, то есть на [[Моноид | моноиде]]. Например, суммирование на множестве натуральных чисел, поиск минимума на любом числовом множестве, перемножение матриц на множестве матриц размера <tex>N*N</tex>, объединение множеств, поиск наибольшего общего делителя на множестве целых чисел и многочленов.
  
При этом дополнительно возможно изменение элементов массива: как изменение значения одного элемента, так и [[Несогласованные поддеревья. Реализация массового обновления | изменение элементов на целом подотрезке массива]], например разрешается присвоить всем элементам <tex>a[i...j]</tex> какое-либо значение, либо прибавить ко всем элементам массива какое-либо число. Структура занимает <tex>O(n)</tex> памяти, а ее построение требует <tex>O(n)</tex> времени.  
+
При этом дополнительно возможно изменение элементов массива: как изменение значения одного элемента, так и [[Несогласованные поддеревья. Реализация массового обновления | изменение элементов на целом подотрезке массива]], например разрешается присвоить всем элементам <tex>a[l \ldots r]</tex> какое-либо значение, либо прибавить ко всем элементам массива какое-либо число. Структура занимает <tex>O(n)</tex> памяти, а ее построение требует <tex>O(n)</tex> времени.  
  
 
==Структура==
 
==Структура==
Структура представляет собой дерево, листьями которого являются элементы исходного массива. Другие вершины этого дерева имеют по 2 ребёнка и содержат результат операции от своих детей (например минимум или сумму). Таким образом, корень содержит результат искомой функции от всего массива <tex>[0...n-1]</tex>, левый ребёнок корня содержит результат функции на <tex>[0...n/2]</tex>, а правый, соответственно результат на <tex>[n/2+1...n-1]</tex>. И так далее, продвигаясь вглубь дерева.
+
Структура представляет собой дерево, листьями которого являются элементы исходного массива. Другие вершины этого дерева имеют по <tex>2</tex> ребенка и содержат результат операции от своих детей (например минимум или сумму). Таким образом, корень содержит результат искомой функции от всего массива <tex>[0\ldots n-1]</tex>, левый ребёнок корня содержит результат функции на <tex dpi=120>[0\ldots\dfrac{n}{2}]</tex>, а правый, соответственно результат на <tex dpi=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 n</tex>. Это сделано, для того чтобы не допустить обращение к несуществующим элементам массива при дальнейшем процессе построения. Пустые элементы необходимо заполнить нейтральными элементами моноида. Тогда для хранения дерева отрезков понадобится массив <tex>t</tex>  из  <tex>2^{k+1}</tex> элементов, поскольку в худшем случае количество вершин в дереве можно оценить суммой <tex>n+n/2+n/4...+1 < 2n</tex>, где <tex>n=2^k</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+\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>a</tex>,  а также переменные <tex>tl</tex> и <tex>tr</tex>, обозначающие границы текущего полуинтервала. Запускаем процедуру построения от корня дерева отрезков (<tex>i=0</tex>,  <tex>tl=0</tex>,  <tex>tr=n</tex>), а сама процедура построения, если её вызвали не от листа, вызывает себя от каждого из двух сыновей и суммирует вычисленные значения, а если её вызвали от листа — то просто записывает в себя значение этого элемента массива (Для этого у нас есть исходный массив <tex> a </tex>). Асимптотика построения дерева отрезков составит, таким образом, <tex>O(n)</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> уже будут заполнены, и мы с легкостью посчитаем функцию от них), а при построении [[Реализация запроса в дереве отрезков сверху | сверху]] спускается от корня к листьям. Особенные изменения появляются в реализации запросов к таким деревьям отрезков.
+
Выделяют два основных способа построения дерева отрезков: построение снизу и построение сверху. При построении [[Реализация запроса в дереве отрезков снизу | снизу]] алгоритм поднимается от листьев к корню (Просто начинаем заполнять элементы массива <tex>t</tex> от большего индекса к меньшему, таким образом при заполнении элемента <tex> i </tex> его дети <tex>2i+1</tex> и <tex>2i+2</tex> уже будут заполнены, и мы с легкостью посчитаем бинарную операцию от них), а при построении [[Реализация запроса в дереве отрезков сверху | сверху]] спускается от корня к листьям. Особенные изменения появляются в реализации запросов к таким деревьям отрезков.
  
[[Файл:Segment_tree.png|Пример дерева отрезков для максимума]]
+
[[Файл:Segment_tree.png|Пример дерева отрезков для минимума]]
  
 
Реализация построения сверху:
 
Реализация построения сверху:
  
  TreeBuild(a[], i, tl, tr)
+
  '''function''' treeBuild('''T''' a[], '''int''' i, '''int''' tl, '''int''' tr): <font color=green>// мы находимся в вершине с номером i, который отвечает за полуинтервал [tl, tr) </font>
  // Мы находимся в элементе с номером i, который отвечает за полуинтервал [tl, tr)
+
    '''if''' tl == tr  
  if (tl = tr) return;
+
        '''return'''
  if (tr - tl = 1)
+
    '''if''' tr - tl == 1
    t[i] = a[tl];
+
        t[i] = a[tl]
  else
+
    '''else'''
    tm = (tl + tr) / 2; //середина отрезка
+
        tm = (tl + tr) / 2                           <font color=green>// середина отрезка</font>
    TreeBuild(a, 2 * i + 1, tl, tm);
+
        treeBuild(a, 2 * i + 1, tl, tm)
    TreeBuild(a, 2 * i + 2, tm, tr);
+
        treeBuild(a, 2 * i + 2, tm, tr)
    t[i] = f(t[2 * i + 1], t[2 * i + 2]);
+
        t[i] = t[2 * i + 1] <tex> \circ </tex> t[2 * i + 2]
  
 
Реализация построения снизу:
 
Реализация построения снизу:
  
  TreeBuild(a[])
+
  '''function''' treeBuild('''T''' a[]):
  for i = n - 1 .. 2 * n - 1
+
    '''for''' i = 0 '''to''' n - 1
  t[i] = a[i - n - 1]
+
        t[n - 1 + i] = a[i]
  for i = n - 2 .. 0
+
    '''for''' i = n - 2 '''downto''' 0
  t[i] = f(t[2 * i + 1], t[2 * i + 2])
+
        t[i] = 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/ Хабрахабр — Статья Максима Ахмедова]
  
===Псевдокод===
+
* [http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006  Дискретная математика: Алгоритмы — Визуализатор дерева отрезков]
<code>
 
  addElement (Tree, ver, x)
 
    if Tree.isFullBinary(ver)
 
      Node tmpRoot = new Node();
 
      roots[Tree.countOfVersions++ + 1] = recAdd(tmpRoot, null, 0, 2 * Tree.size(ver), x, Tree.size(ver) + 1);
 
    else
 
      // k : 2 ^ (k - 1) <= Tree.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)
 
    // Мы находимся в узле node, который отвечает за полуинтервал (l, r]
 
    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://e-maxx.ru/algo/segment_tree  MAXimal :: algo :: Дерево отрезков]
    //изменить i-ый элемент на x
 
    if r - 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);
 
      tmp.valueOfFunction = f(tmp.L, tmp.R);
 
      if(node.parent == null)
 
        roots[Tree.countOfVersions++ + 1] = tmp;
 
      return tmp;
 
</code>
 
Здесь функции <tex>recAdd()</tex> и <tex>change()</tex> возвращает указатель на узел новой ветки.
 
[[Файл:persist.png]]
 
  
==Ссылки==
+
* [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://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006 - Визуализатор дерева отрезков]
 
  
[http://e-maxx.ru/algo/segment_tree - MAXimal :: algo :: Дерево отрезков]
+
* [http://ru.wikipedia.org/wiki/Моноид Википедия — Моноид]
 
 
[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/Моноид - Моноид — Википедия]
 
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дерево отрезков]]
 
[[Категория: Дерево отрезков]]
 +
[[Категория: Структуры данных]]

Версия 20:59, 24 декабря 2018

Дерево отрезков (англ. Segment tree) — это структура данных, которая позволяет за асимптотику [math]O(\log n)[/math] реализовать любые операции, определяемые на множестве, на котором данная операция ассоциативна, и существует нейтральный элемент относительно этой операции, то есть на моноиде. Например, суммирование на множестве натуральных чисел, поиск минимума на любом числовом множестве, перемножение матриц на множестве матриц размера [math]N*N[/math], объединение множеств, поиск наибольшего общего делителя на множестве целых чисел и многочленов.

При этом дополнительно возможно изменение элементов массива: как изменение значения одного элемента, так и изменение элементов на целом подотрезке массива, например разрешается присвоить всем элементам [math]a[l \ldots r][/math] какое-либо значение, либо прибавить ко всем элементам массива какое-либо число. Структура занимает [math]O(n)[/math] памяти, а ее построение требует [math]O(n)[/math] времени.

Структура

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

Построение дерева

Пусть исходный массив [math]a[/math] состоит из [math]n[/math] элементов. Для удобства построения увеличим длину массива [math]a[/math] так, чтобы она равнялась ближайшей степени двойки, т.е. [math]2^k[/math], где [math]2^k \geqslant n[/math]. Это сделано, для того чтобы не допустить обращение к несуществующим элементам массива при дальнейшем процессе построения. Пустые элементы необходимо заполнить нейтральными элементами моноида. Тогда для хранения дерева отрезков понадобится массив [math]t[/math] из [math]2^{k+1}[/math] элементов, поскольку в худшем случае количество вершин в дереве можно оценить суммой [math]n+\dfrac{n}{2}+\dfrac{n}{4} \ldots +1 \lt 2n[/math], где [math]n=2^k[/math]. Таким образом, структура занимает линейную память.

Процесс построения дерева заключается в заполнении массива [math]t[/math]. Заполним этот массив таким образом, чтобы [math]i[/math]-й элемент являлся бы результатом некоторой бинарной операции (для каждой конкретной задачи своей) от элементов c номерами [math]2i+1[/math] и [math]2i+2[/math], то есть родитель являлся результатом бинарной операции от своих сыновей (обозначим в коде эту операцию как "[math] \circ [/math]"). Один из вариантов — делать рекурсивно. Пусть у нас имеются исходный массив [math]a[/math], а также переменные [math]\mathtt{tl}[/math] и [math]\mathtt{tr}[/math], обозначающие границы текущего полуинтервала. Запускаем процедуру построения от корня дерева отрезков ([math]i=0[/math], [math]\mathtt{tl}=0[/math], [math]\mathtt{tr}=n[/math]), а сама процедура построения, если её вызвали не от листа, вызывает себя от каждого из двух сыновей и суммирует вычисленные значения, а если её вызвали от листа — то просто записывает в себя значение этого элемента массива (Для этого у нас есть исходный массив [math] a [/math]). Асимптотика построения дерева отрезков составит, таким образом, [math]O(n)[/math].

Выделяют два основных способа построения дерева отрезков: построение снизу и построение сверху. При построении снизу алгоритм поднимается от листьев к корню (Просто начинаем заполнять элементы массива [math]t[/math] от большего индекса к меньшему, таким образом при заполнении элемента [math] i [/math] его дети [math]2i+1[/math] и [math]2i+2[/math] уже будут заполнены, и мы с легкостью посчитаем бинарную операцию от них), а при построении сверху спускается от корня к листьям. Особенные изменения появляются в реализации запросов к таким деревьям отрезков.

Пример дерева отрезков для минимума

Реализация построения сверху:

function treeBuild(T a[], int i, int tl, int tr):  // мы находимся в вершине с номером i, который отвечает за полуинтервал [tl, tr) 
    if tl == tr 
        return
    if tr - tl == 1
        t[i] = a[tl]
    else
        tm = (tl + tr) / 2                            // середина отрезка
        treeBuild(a, 2 * i + 1, tl, tm)
        treeBuild(a, 2 * i + 2, tm, tr)
        t[i] = t[2 * i + 1] [math] \circ [/math] 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] [math] \circ [/math] t[2 * i + 2]

См. также

Источники информации