Дерево отрезков

Общая идея

Очень похоже на sparse table - хотим предподсчитывать какие-то значения для отрезков, и обновлять их при изменении дерева.

Замечание: рассматриваем на примере задачи RMQ из конспекта про sparse table

Структура

На нижнем уровне располагаются элементы массива, на уровень выше - узлы, в которых минимум из двух элементов, на уровень выше - минимум из соответствующих соседей предыдущего уровня и так далее. Рисунок для случая, когда количество элементов в массиве - степень двойки. (vis. 18:54)
Разумеется, уровней всего O(log n). На i-м уровне, начиная от самого нижнего, n / 2^i элементов. Таким образом, все дерево можно построить (просто сумма членов геометрической прогрессии) за O(n).

Обработка запроса

Общая идея: процедура getMin начинает от корня дерева и рекурсивно спускается в те отрезки, которые ее интересуют. Пусть мы находимся в вершине x, которая соответствует полуинтервалу TreeSeg = [L_tree, R_tree), а нам нужен минимум на полуинтервале QuerySeg = [L_q, R_q). Строго говоря, возможны три случая:
1. TreeSeg < QuerySeg. Тогда необходимо вернуть значение из вершины.
2. TreeSeg () QuerySeg = (/). Необходимо вернуть какую-то большую константу IntMax, или какой-то флаг, показывающий, что отрезки не пересекаются - чтобы уже "вышестоящий орган" думал над тем, что с этим знанием делать.
3. TreeSeg () QuerySe != (/). Тогда, разумеется, для обработки запроса необходимо вернуть min (getMin (left_half (x)), getMin (right_half (x))). Заметим, что в силу того что left_half и right_half не пересекаются, мы в будущем сможем решать более сложные задачи с помощью этой же структуры.

Лемма 1

Каждый такой запрос выполняется за O(log n).

[развернуть]

Доказательство

Понятно, что оценка асимптотики алгоритма сводится к подсчету количества рекурсий, которые наша процедура потребует для выполнения. Рассмотрим произвольный уровень нашего дерева при запросе. На нем мы сделаем не более двух рекурсий вниз по дереву (случай 3). Таким образом, количество рекурсий ограничено O(1) * O(height) = O(log n).

Изменение дерева

Замечание: на данном этапе предлагается перейти к произвольной функции f элементов на отрезке. Разумеется, нам подойдут не все функции. Необходимо, чтобы эта функция была ассоциативной, поскольку иначе мы не сможет "расставлять скобки" при сведении этой задачи к меньшим.

Оговорка: мы храним наше дерево в виде массива - по аналогии с бинарной кучей.

Итак, обрабатываем запрос вида change (i, new_value). Существуют два подхода:
1. "Изменение снизу".
Зная номер вершины i мы можем пересчитать все значения дерева, которые идут на пути от корня до этой вершины (напомним, что индекс родителя при нашей оговорке мы найдем как i / 2). Эта схема плоха тем, что работает только для случая, когда количество элементов - степень двойки.
2. "Изменение сверху".
Аналогично процедуре обработки запроса, мы рекурсивно спускаемся в нужное нам поддерево, переподсчитываем там нашу функцию, после этого обновляем значение в текущей вершины и возвращаем его.

Изменение элементов на подотрезке

Пусть нам поступает запрос на присвоение всем элементам с индексами от L до R значения new_value. Вновь применим идею отложенной операции. Будем рекурсивно спускаться от корня пока весь соответствующий текущей вершине полуинтервал не будет лежать в [L, R); когда это произошло, сохраним в этой вершине запрос на изменение.
Тогда нужно понять, как это повлияет на процедуру обработки запроса. Разумеется, изменится случай 1 - сейчас нам придется учитывать не только значение вершины, но и эту отложенную операцию, что, впрочем, несильно усложняет дело. Также необходимо в случае 3 "протолкнуть" отложенную операцию в сыновей. Понятно, что никакую асимптотику это нарушить не может. Но здесь важно не забыть после рассмотрения случаев 1, 2, 3 обновить значение в текущей вершине на основе обновленной информации о детях и той ленивой метке, которая сейчас есть. И только после этого можно безопасно возвращаться на уровень выше.