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

Общая идея

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