Изменения

[[Файл:Segment_tree.jpg|right|400px|thumb|Пример дерева отрезков для вычисления сумм]]'''Дерево отрезков''' {{---}} это структура данных, которая позволяет эффективно (за асимптотику <tex>O(\log n))</tex> реализовать операции следующего вида: нахождение суммы (задача RSQ), минимума или максимума (задача RMQ) элементов массива в заданном отрезке (<tex>a[i...j]</tex>, где <tex>i</tex> и <tex>j</tex> поступают на вход алгоритма), при этом дополнительно возможно изменение элементов массива: как изменение значения одного элемента, так и изменение элементов на целом подотрезке массива (т.е. разрешается присвоить всем элементам <tex>a[i...j]</tex> какое-либо значение, либо прибавить ко всем элементам массива какое-либо число). Структура занимает <tex>O(n)</tex> памяти и выстраивается из массива за <tex>O(n)</tex>.

[[Файл:Segment_tree.jpg|right|400px|thumb|Пример дерева отрезков для вычисления сумм]]Структура представляет собой дерево, листьями которого являются элементы исходного массива. Другие вершины этого дерева имеют по 2 ребёнка и содержат сумму или минимум/максимум своих детей (в зависимости от поставленной задачи). Таким образом, корень содержит результат искомой функции от всего массива <tex>[0...n-1]</tex>, левый ребёнок корня содержит результат функции на <tex>[0...n/2]</tex>, а правый, соответственно результат на <tex>[n/2+1...n-1]</tex>. И так далее, продвигаясь вглубь дерева.