Изменения
Нет описания правки
'''Дерево отрезков''' (англ. ''Segment tree'') {{---}} это структура данных, которая позволяет за асимптотику <tex>O(\log n)</tex> реализовать любые операции, определяемые на [[Моноид | моноиде]]множестве, на котором данная операция ассоциативна, и существует нейтральный элемент относительно этой операции. Например, следующего вида: нахождение суммы (задача RSQ)суммирование на множестве натуральных чисел, поиск минимума или максимума (задача RMQ) элементов массива на множестве, включающем в заданном отрезке (<tex>a[l...r]</tex>себя только отрицательные числа и ноль, где <tex>l</tex> и <tex>r</tex> поступают перемножение матриц на вход алгоритма)множестве матриц размера N*N.
При этом дополнительно возможно изменение элементов массива: как изменение значения одного элемента, так и [[Несогласованные поддеревья. Реализация массового обновления | изменение элементов на целом подотрезке массива]], например разрешается присвоить всем элементам <tex>a[l...r]</tex> какое-либо значение, либо прибавить ко всем элементам массива какое-либо число. Структура занимает <tex>O(n)</tex> памяти, а ее построение требует <tex>O(n)</tex> времени.
