Изменения

Перейти к: навигация, поиск

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

146 байт убрано, 03:50, 30 апреля 2011
Построение дерева
Далее будем считать, что дерево выстраиваем для задачи вычисления суммы на отрезке. Для минимума и максимума операция построения проделывается аналогично.
Процесс построения дерева заключается в заполнении массива <tex>t</tex>. Заполним этот массив таким образом, чтобы <tex>i</tex>-й элемент являлся бы суммой элемента c номером <tex>2i</tex> и элемента с номером <tex>2i+1</tex> (или соответственно с номерами <tex>2i+1</tex> и <tex>2i+2</tex>, если первый индекс массива 0), т.е. родитель являлся бы суммой своих сыновей. Лучше всего эту процедуру делать рекурсивно. Создадим функцию от исходного массива <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-1</tex>), а сама процедура построения, если её вызвали не от листа, вызывает себя от каждого из двух сыновей и суммирует вычисленные значения, а если её вызвали от листа — то просто записывает в себя значение этого элемента массива. Асимптотика построения дерева отрезков составит, таким образом, <tex>O(n)</tex>.
Реализация:
else
tm = (tl + tr) / 2; //середина отрезка
TreeBuild(a, 2*i+1, tl, tm); TreeBuild(a, 2*i+21, tm+1, tr);
t[i] = t[2*i+1] + t[2*i+2];
Анонимный участник

Навигация