Викиконспекты - Вклад участника [ru]

Дерево отрезков. Построение

2012-05-17T15:18:22Z

178.66.82.118: /* Построение дерева */

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

==Построение дерева==
[[Файл:Segment_tree.jpg|right|380px|thumb|Пример дерева отрезков для вычисления сумм]]Пусть исходный массив <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>t</tex>. Заполним этот массив таким образом, чтобы <tex>i</tex>-й элемент являлся бы суммой элемента c номером <tex>2i+1</tex> и элемента с номером <tex>2i+2</tex>, т.е. родитель являлся бы суммой своих сыновей. Лучше всего эту процедуру делать рекурсивно. Создадим функцию от исходного массива <tex>a</tex>, переменной <tex>i</tex>, обозначающей номер элемента в массиве <tex>t</tex>, а так же переменные <tex>tl</tex> и <tex>tr</tex>, обозначающие границы текущего полуинтервала. Запускаем процедуру построения от корня дерева отрезков (<tex>i=0</tex>, <tex>tl=0</tex>, <tex>tr=n</tex>), а сама процедура построения, если её вызвали не от листа, вызывает себя от каждого из двух сыновей и суммирует вычисленные значения, а если её вызвали от листа — то просто записывает в себя значение этого элемента массива. Асимптотика построения дерева отрезков составит, таким образом, <tex>O(n)</tex>.

Реализация:

TreeBuild(a[], 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] = f(t[2*i+1], t[2*i+2]);

Выделяют два основных способа построения дерева отрезков: построение снизу и построение сверху. При построении [[Реализация запроса в дереве отрезков снизу | снизу]] алгоритм поднимается от листьев к корню, а при построении [[Реализация запроса в дереве отрезков сверху | сверху]] спускается от корня к листьям, как указано в реализации. Особенные изменения появляются в реализации запросов к таким деревьям отрезков.

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

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Дерево отрезков]]

Дерево отрезков. Построение

2012-05-17T15:15:55Z

178.66.82.118:

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

==Построение дерева==
[[Файл:Segment_tree.jpg|right|380px|thumb|Пример дерева отрезков для вычисления сумм]]Пусть исходный массив <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>t</tex>. Заполним этот массив таким образом, чтобы <tex>i</tex>-й элемент являлся бы суммой элемента c номером <tex>2i</tex> и элемента с номером <tex>2i+1</tex>, т.е. родитель являлся бы суммой своих сыновей. Лучше всего эту процедуру делать рекурсивно. Создадим функцию от исходного массива <tex>a</tex>, переменной <tex>i</tex>, обозначающей номер элемента в массиве <tex>t</tex>, а так же переменные <tex>tl</tex> и <tex>tr</tex>, обозначающие границы текущего полуинтервала. Запускаем процедуру построения от корня дерева отрезков (<tex>i=1</tex>, <tex>tl=0</tex>, <tex>tr=n</tex>), а сама процедура построения, если её вызвали не от листа, вызывает себя от каждого из двух сыновей и суммирует вычисленные значения, а если её вызвали от листа — то просто записывает в себя значение этого элемента массива. Асимптотика построения дерева отрезков составит, таким образом, <tex>O(n)</tex>.

Реализация:

TreeBuild(a[], 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] = f(t[2*i+1], t[2*i+2]);

Выделяют два основных способа построения дерева отрезков: построение снизу и построение сверху. При построении [[Реализация запроса в дереве отрезков снизу | снизу]] алгоритм поднимается от листьев к корню, а при построении [[Реализация запроса в дереве отрезков сверху | сверху]] спускается от корня к листьям, как указано в реализации. Особенные изменения появляются в реализации запросов к таким деревьям отрезков.

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

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Дерево отрезков]]

Дерево отрезков. Построение

2012-05-17T15:12:14Z

178.66.82.118: /* Построение дерева */

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

==Построение дерева==
[[Файл:Segment_tree.jpg|right|380px|thumb|Пример дерева отрезков для вычисления сумм]]Пусть исходный массив <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>t</tex>. Заполним этот массив таким образом, чтобы <tex>i</tex>-й элемент являлся бы суммой элемента c номером <tex>2i</tex> и элемента с номером <tex>2i+1</tex>, т.е. родитель являлся бы суммой своих сыновей. Лучше всего эту процедуру делать рекурсивно. Создадим функцию от исходного массива <tex>a</tex>, переменной <tex>i</tex>, обозначающей номер элемента в массиве <tex>t</tex>, а так же переменные <tex>tl</tex> и <tex>tr</tex>, обозначающие границы текущего полуинтервала. Запускаем процедуру построения от корня дерева отрезков (<tex>i=1</tex>, <tex>tl=0</tex>, <tex>tr=n</tex>), а сама процедура построения, если её вызвали не от листа, вызывает себя от каждого из двух сыновей и суммирует вычисленные значения, а если её вызвали от листа — то просто записывает в себя значение этого элемента массива. Асимптотика построения дерева отрезков составит, таким образом, <tex>O(n)</tex>.

Реализация:

TreeBuild(a[], 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] = f(t[2*i+1], t[2*i+2]);

Выделяют два основных способа построения дерева отрезков: построение снизу и построение сверху. При построении [[Реализация запроса в дереве отрезков снизу | снизу]] алгоритм поднимается от листьев к корню, а при построении [[Реализация запроса в дереве отрезков сверху | сверху]] спускается от корня к листьям, как указано в реализации. Особенные изменения появляются в реализации запросов к таким деревьям отрезков.

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

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Дерево отрезков]]

Дерево отрезков. Построение

2012-05-17T15:10:51Z

178.66.82.118:

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

==Построение дерева==
[[Файл:Segment_tree.jpg|right|380px|thumb|Пример дерева отрезков для вычисления сумм]]Пусть исходный массив <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>t</tex>. Заполним этот массив таким образом, чтобы <tex>i</tex>-й элемент являлся бы суммой элемента c номером <tex>2i</tex> и элемента с номером <tex>2i+1</tex>, т.е. родитель являлся бы суммой своих сыновей. Лучше всего эту процедуру делать рекурсивно. Создадим функцию от исходного массива <tex>a</tex>, переменной <tex>i</tex>, обозначающей номер элемента в массиве <tex>t</tex>, а так же переменные <tex>tl</tex> и <tex>tr</tex>, обозначающие границы текущего полуинтервала. Запускаем процедуру построения от корня дерева отрезков (<tex>i=1</tex>, <tex>tl=0</tex>, <tex>tr=n</tex>), а сама процедура построения, если её вызвали не от листа, вызывает себя от каждого из двух сыновей и суммирует вычисленные значения, а если её вызвали от листа — то просто записывает в себя значение этого элемента массива. Асимптотика построения дерева отрезков составит, таким образом, <tex>O(n)</tex>.

Реализация:

TreeBuild(a[], 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] = f(t[2*i+1], t[2*i+2]);

Выделяют два основных способа построения дерева отрезков: построение снизу и построение сверху. При построении [[Реализация запроса в дереве отрезков снизу | снизу]] алгоритм поднимается от листьев к корню, как в [[Задача о паросочетании максимального веса в дереве, амортизированные оценки для ДП на дереве | динамике по поддереву]], а при построении [[Реализация запроса в дереве отрезков сверху | сверху]] спускается от корня к листьям, как указано в реализации. Особенные изменения появляются в реализации запросов к таким деревьям отрезков.

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

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Дерево отрезков]]