Изменения

|definition= '''Дерево отрезков''' {{---}} это структура данных, которая позволяет за асимптотику <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>.