Задачи RMQ и LCA

Динамическая задача RMQ/RSQ: дерево отрезков, оценка $O(\log n)$ для запросов суммы/минимума и изменения элемента.
Статический вариант задачи RMQ: полное предвычисление ($O(n^2)$ на предобработку, $O(1)$ на запрос), метод разреженной таблицы ($O(n\log n)$ на предобработку, $O(1)$ на запрос). Задача LCA: эйлеров обход дерева, сведение к задаче RMQ.