Изменения

[[Файл:Segment_tree.jpg|right|350px380px|thumb|Пример дерева отрезков для вычисления сумм]]Пусть исходный массив <tex>a</tex> состоит из <tex>n</tex> элементов. Для удобства построения увеличим длину массива <tex dpi>a</tex> так, чтобы она равнялась ближайшей степени двойки, т.е. <tex>2^k</tex>, где <tex>2^k \ge n</tex>. Это сделано, для того чтобы не допустить обращение к несуществующим элементам массива при дальнейшем процессе построения. Пустые элементы можно заполнить нулями или бесконечностями (за бесконечностью стоит понимать, например, число, больше которого в данных ничего не появится) в зависимости от поставленной задачи. Тогда для хранения дерева отрезков понадобится массив <tex>t</tex> из <tex>2^{k+1}</tex> элементов, поскольку в худшем случае количество вершин в дереве можно оценить суммой <tex>n+n/2+n/4...+1 < 2n</tex>, где <tex>n=2^k</tex>. Таким образом, структура занимает линейную память.