Изменения

'''Дерево отрезков''' {{---}} это структура данных, которая позволяет эффективно (за асимптотику <tex dpi = "140">O(log n))</tex> реализовать операции следующего вида: нахождение суммы (задача RSQ), минимума или максимума (задача RMQ) элементов массива в заданном отрезке (<tex dpi = "140">a[i...j]</tex>, где <tex dpi = "140">i</tex> и <tex dpi = "140">j</tex> поступают на вход алгоритма), при этом дополнительно возможно изменение элементов массива: как изменение значения одного элемента, так и изменение элементов на целом подотрезке массива (т.е. разрешается присвоить всем элементам <tex dpi = "140">a[i...j]</tex> какое-либо значение, либо прибавить ко всем элементам массива какое-либо число). Структура занимает <tex dpi = "140">O(n)</tex> памяти и выстраивается из массива за <tex dpi = "140">O(n)</tex>.