Изменения

Процесс построения дерева заключается в заполнении массива <tex dpi = "140">t</tex>. Заполним этот массив таким образом, чтобы <tex dpi = "140">i</tex>-й элемент являлся бы суммой элемента c номером <tex dpi = "140">2i</tex> и элемента с номером <tex dpi = "140">2i+1</tex>, т.е. родитель являлся бы суммой своих сыновей. Лучше всего эту процедуру делать рекурсивно. Создадим функцию от исходного массива <tex dpi = "140">a</tex>, переменной <tex dpi = "140">i</tex>, обозначающей номер элемента в массиве <tex dpi = "140">t</tex>, а так же переменные <tex dpi = "140">tl</tex> и <tex dpi = "140">tr</tex>, обозначающие соответственно левую и правую границы текущего отрезка. Запускаем процедуру построения от корня дерева отрезков (<tex dpi = "140">i=1</tex>, <tex dpi = "140">tl=0</tex>, <tex dpi = "140">tr=n-1</tex>), а сама процедура построения, если её вызвали не от листа, вызывает себя от каждого из двух сыновей и суммирует вычисленные значения, а если её вызвали от листа — то просто записывает в себя значение этого элемента массива. Асимптотика построения дерева отрезков составит, таким образом, <tex dpi = "140">O(n)</tex>.