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

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

Дерево отрезков — это структура данных, которая позволяет за асимптотику [math]O(\log n)[/math] реализовать любые операции, определяемые на моноиде. Например, следующего вида: нахождение суммы (задача RSQ), минимума или максимума (задача RMQ) элементов массива в заданном отрезке ([math]a[i...j][/math], где [math]i[/math] и [math]j[/math] поступают на вход алгоритма).

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

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

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

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

Ссылки

- Визуализатор дерева отрезков

- MAXimal :: algo :: Дерево отрезков

- Дерево отрезков — Википедия

- Моноид — Википедия