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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Построение дерева)
м (rollbackEdits.php mass rollback)
 
(не показаны 23 промежуточные версии 9 участников)
Строка 1: Строка 1:
'''Дерево отрезков''' (англ. ''Segment tree'') {{---}} это структура данных, которая позволяет за асимптотику <tex>O(\log n)</tex> реализовать любые операции, определяемые на [[Моноид | моноиде]]. Например, следующего вида: нахождение суммы (задача RSQ), минимума или максимума (задача RMQ) элементов массива в заданном отрезке (<tex>a[l...r]</tex>, где <tex>l</tex> и <tex>r</tex> поступают на вход алгоритма)
+
'''Дерево отрезков''' (англ. ''Segment tree'') {{---}} это структура данных, которая позволяет за асимптотику <tex>O(\log n)</tex> реализовать любые операции, определяемые на множестве, на котором данная операция ассоциативна, и существует нейтральный элемент относительно этой операции, то есть на [[Моноид | моноиде]]. Например, суммирование на множестве натуральных чисел, поиск минимума на любом числовом множестве, перемножение матриц на множестве матриц размера <tex>N*N</tex>, объединение множеств, поиск наибольшего общего делителя на множестве целых чисел и многочленов.
  
При этом дополнительно возможно изменение элементов массива: как изменение значения одного элемента, так и [[Несогласованные поддеревья. Реализация массового обновления | изменение элементов на целом подотрезке массива]], например разрешается присвоить всем элементам <tex>a[l...r]</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 dpi=120>[0...\dfrac{n}{2}]</tex>, а правый, соответственно результат на <tex dpi=120>[\dfrac{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+\dfrac{n}{2}+\dfrac{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''' tr - tl == 1
  '''if''' tl == tr
+
        t[i] = a[tl]
     '''return'''
+
    '''else'''
  '''if''' tr - tl == 1
+
        tm = (tl + tr) / 2                           <font color=green>// середина отрезка</font>
    t[i] = a[tl]
+
        treeBuild(a, 2 * i + 1, tl, tm)
  '''else'''
+
        treeBuild(a, 2 * i + 2, tm, tr)
    tm = (tl + tr) / 2 //середина отрезка
+
        t[i] = t[2 * i + 1] <tex> \circ </tex> t[2 * i + 2]
    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]
 
  
 
Реализация построения снизу:
 
Реализация построения снизу:
  
<code>
+
  '''function''' treeBuild('''T''' a[]):
  treeBuild(a[])
+
     '''for''' i = 0 '''to''' n - 1
     '''for''' i = 0 .. n - 1
 
 
         t[n - 1 + i] = a[i]
 
         t[n - 1 + i] = a[i]
     '''for''' i = n - 2 .. 0
+
     '''for''' i = n - 2 '''downto''' 0
 
         t[i] = t[2 * i + 1] <tex> \circ </tex> t[2 * i + 2]
 
         t[i] = t[2 * i + 1] <tex> \circ </tex> t[2 * i + 2]
</code>
 
 
==Персистентное дерево отрезков==
 
{{Определение
 
|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>. Иначе, сделаем копию корня исходной версии. Добавим корень в конец массива корней. Далее, спускаясь от корня к первому свободному листу, будем создавать несуществующие узлы и клонировать существующие. После этого в новой ветке необходимо обновить значение функции и некоторые указатели дочерних элементов. Поэтому, возвращаясь из рекурсии, будем менять один указатель на только что созданную или скопированную вершину, а также обновим значение функции, для которой строилось дерево. После этой операции в дереве появится новая версия, содержащая вставленный элемент.
 
 
===Изменение элемента===
 
Для того, чтобы изменить элемент в персистентном дереве отрезков, необходимо сделать следующие действия: спустимся в дереве от корня нужной версии  до требуемого элемента, скопируем его, изменим значение, и, поднимаясь по дереву, будем клонировать узлы. При этом необходимо менять указатель на одного из детей на узел, созданный при предыдущем клонировании. После копирования корня, добавим новый корень в конец массива корней.
 
 
[[Файл:persist.png]]
 
 
Здесь изображено персистентное дерево отрезков с операцией минимум, в котором изначально было 3 вершины. Сперва к нему была добавлена вершина со значением 2, а потом изменена вершина со значением 7. Цвет ребер и вершин соответствует времени их появления. Синий цвет элементов означает, что они были изначально, зеленый - что они появились после добавления, а оранжевый - что они появились после изменения элемента.
 
  
 
==См. также==
 
==См. также==
Строка 70: Строка 41:
 
*[[Несогласованные поддеревья. Реализация массового обновления]]
 
*[[Несогласованные поддеревья. Реализация массового обновления]]
  
==Ссылки==  
+
==Источники информации==  
* [http://habrahabr.ru/post/115026/ Статья Максима Ахмедова]
+
* [http://habrahabr.ru/post/115026/ Хабрахабр — Статья Максима Ахмедова]
  
* [http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006  Визуализатор дерева отрезков]
+
* [http://rain.ifmo.ru/cat/view.php/vis/trees/segment-2006  Дискретная математика: Алгоритмы — Визуализатор дерева отрезков]
  
 
* [http://e-maxx.ru/algo/segment_tree  MAXimal :: algo :: Дерево отрезков]
 
* [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/%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/Моноид  Моноид — Википедия]
+
* [http://ru.wikipedia.org/wiki/Моноид  Википедия — Моноид]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дерево отрезков]]
 
[[Категория: Дерево отрезков]]
 +
[[Категория: Структуры данных]]

Текущая версия на 19:43, 4 сентября 2022

Дерево отрезков (англ. 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 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]

См. также

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