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

Определение:

Дерево отрезков — это структура данных, которая позволяет за асимптотику реализовать любые операции, определяемые на моноиде. Например, следующего вида: нахождение суммы (задача RSQ), минимума или максимума (задача RMQ) элементов массива в заданном отрезке (, где и поступают на вход алгоритма).

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

Структура

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

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

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

Пусть исходный массив состоит из элементов. Для удобства построения увеличим длину массива так, чтобы она равнялась ближайшей степени двойки, т.е. , где . Это сделано, для того чтобы не допустить обращение к несуществующим элементам массива при дальнейшем процессе построения. Пустые элементы необходимо заполнить нейтральными элементами моноида. Тогда для хранения дерева отрезков понадобится массив из элементов, поскольку в худшем случае количество вершин в дереве можно оценить суммой , где . Таким образом, структура занимает линейную память.

Далее будем считать, что дерево выстраиваем для задачи вычисления суммы на отрезке. Для минимума и максимума операция построения проделывается аналогично.

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

Реализация:

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]);

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