Дерево отрезков — это структура данных, которая позволяет эффективно (т.е. за асимптотику O (log n)) реализовать операции следующего вида: нахождение суммы/минимума элементов массива в заданном отрезке (a[l…r], где l и r поступают на вход алгоритма), при этом дополнительно возможно изменение элементов массива: как изменение значения одного элемента, так и изменение элементов на целом подотрезке массива (т.е. разрешается присвоить всем элементам a[l...r] какое-либо значение, либо прибавить ко всем элементам массива a[l...r] какое-либо число).
Во всей статье Дерево Отрезков будет обозначаться как ДО.
P.S. ДО можно писать или на отрезках или на полуинтервалах,то есть вершина будет хранить какую-нибудь функцию на отрезке [l;r],если писать на отрезках или на полуинтервале [l;r),если писать
на полуинтервалах.Большой разницы нет,но я буду объяснять на полуинтервалах.
Давайте разберем ДО на примере суммы на отрезке и прибавления на отрезке.
Давайте разобьём начальный массив размера n на две примерно равные половинки:[0;n/2) и [n/2;n).Данные половинки разобьём так же на половинки.И так пока не дойдем до размера 1.При этом считаем функцию на всех этих половинках,размера n, n/2, n/4 и т.д.Так будет выглядить дерево для массива {1, -5, 6, 10}.Сверху вершины указаны границы ее поддерева,в самой ве ршине сумма.
Из рисунка видно,что чтобы посчитать функцию в текущей вершине надо пересчитать через функции от детей.Например сумма в текущей вершине – это сумма в левом ребенке + сумма в правом ребенке.Минимум в текущей вершине – это минимум из минимумов детей и т.п.
Так же есть небольшое неудобство если размер массива это не степень двойки,тогда дерево не будет таким “идеальным”.Но на практике это никакого неудобства не приносит.
Теперь обратимся к коду и реализации такого дерева.Давайте заведем структуру Node,в которой будем хранить границы ее поддерева,функцию на поддереве(например сумму), ссылки на ее детей(как это реализовать будет чуть позже), и поле add,в котором будем хранить сколько нужно прибавить ко всем элементам поддерева(чуть позже объясняется зачем это нужно). В коде это выглядит примерно так. (Если кто не знает поле – это переменная в структуре).
Поля Node* left и Node* right это указатели на левого и правого сыновей соответственно.Поля int lb, int rb границы вершины,sum – сумма на подмассива [lb;rb), поле add объясняется чуть позже.
Но есть один вопрос: что делать с листами дерева,у них же нет сыновей?Следовательно придется if’ать и пересчитывать функцию не через детей,а просто забивать элемент массива(так как границы у листа [i;i+1)).Давайте вместо этого создадим фиктивную вершину,в которой в поле результата функции будет какой-нибудь нейтральный элемент(для суммы это 0,для произведения 1,для минимума бесконечность).Код:
Кто не знает {} означает конструктор,то есть таким образом создается указатель на структуру у которой поля left и right равны NULL, поля lb, rb, sum, add равны 0.NULL это указатель на пустоту.
Теперь,после создания самой вершины, давайте построим из них само дерево.Напишем функцию build,которая будет собственно строить саму структуру дерево,пока без подсчета функции.Будем делать это следующим образом: будем рекурсивно передавать в функцию границы текущей вершины.Если наша текущая вершина лист,то давайте вернем новую вершину,границы в которой будут нашими текщими границами,сумма 0,поле add так же 0(нам ничего пока что прибавлять не нужно),а дети фиктивные вершины,то есть Empty.Если же текушая вершина не лист,то давайте запустим нашу функцию build(l, mid) и build(mid, r), где mid = (l + r) / 2.Таким образом мы построим сыновей текущей вершины.После построения вернем вершину,у которой левый ребенок будет результат выполения build(l, mid),правый ребенок результатом выполения build(mid, r),поля lb и rb нашими текущими вершинами,а поля sum и add так же 0.В коде это выглядит так:
Например так будет выглядить дерево при массиве размера 4.То есть мы запустим функцию build(0, 4).
Теперь давайте посчитаем асимптотику функции build для массива размера n.Как было описано ранее начальный массив мы поделим на 2 примерно равные части,затем эти части на еще 2 и так далее,пока не дойдем до размера 1.Сколько раз мы поделим отрезки на 2?Очевидно что log(n).Следовательно высота нашего дерева будет не больше log(n),и на каждом уровне не больше n вершин,следовательно итоговая асимптотика O(nlogn).
Теперь нам надо изменить наши значения в дереве.Можно это делать вручную,просто рекурсивно спускаться по дереву и когда дошли до листа,то присвоить ему элемент соответствующий ему в массиве,а когда будем возвращаться рекурсивно обратно пересчитывать функцию в текущей вершине.В коде примерно так:
Асимптотика так же будет log(n),так как высота не больше log(n).
Но давайте попробуем реализовать массовое прибавление на полуинтервале [l;r) за асимптотику log(n).Тогда прибавление к одному элементу мы сможем делать как массовое прибавление на отрезке длины 1.Для этого нам и пригодится поле add.Давайте делать следующее: нам пришел запрос прибавления на полуинтервале [l;r) числа d.Давайте не будем честно идти и прибавлять на всем полуинтервале число d.А будем просто запоминать,что мы должны прибавить.Поле add и будет отвечать за данное запоминание.
Для начала давайте реализуем такую функцию,которая бы “проталкивала” информацию о прибавлении детям данной вершины.Так как если нашей текущей вершине надо что-то прибавить,то и ее детям надо прибавить абсолютно тоже самое(это видно из структуры самого дерева).Так же в этой функции будем сразу пересчитывать функцию всего поддерева.Это делается довольно очевидно.Как изменится сумма на отрезке размера size,если ко всем его элементам прибавится одно и тоже число d?Логично,что прибавиться d * size.Если бы мы считали не сумму,то пересчет выводился бы смотря от функции.Например,если бы был минимум,то к минимуму бы просто прибавилось число d.Код:
Теперь приведу саму функцию прибавления на отрезке:
Асимптотика данной функции O(logn).