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

Общая идея

Очень похоже на 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 элементов на отрезке. Разумеется, нам подойдут не все функции. Необходимо, чтобы эта функция была ассоциативной, поскольку иначе мы не сможет "расставлять скобки" при сведении этой задачи к меньшим.