Изменения

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

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

41 байт убрано, 22:03, 25 мая 2012
Построение дерева
Далее будем считать, что дерево выстраиваем для задачи вычисления суммы на отрезке. Для минимума и максимума операция построения проделывается аналогично.
Процесс построения дерева заключается в заполнении массива <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> a </tex>. Асимптотика построения дерева отрезков составит, таким образом, <tex>O(n)</tex>.
Реализация:
Анонимный участник

Навигация