День 1. RMQ & LCA

1. С/C++: #define _GLIBCXX_DEBUG, vector-а, никаких глобальных переменных, struct SparseTable
2. RMQ: Формулировка. Простые решение: [O(n²), O(1)] и [O(n), O(n)], деревом отрезков за [O(n), O(logn)]
3. RMQ: Sparse table: [nlogn, 1], [n, loglogn], [nlog*n, log*n]
4. RMQ±1 за [n, 1]
5. LCA: Формулирова. Решение за O(distance).
6. LCA: Двоичные подъёмы [nlogn, logn]
7. LCA → RMQ±1 за O(n), итого решение LCA за [O(n), O(1)] (Эйлеров обход)
8. Эйлеров обход − функция на поддереве это теперь функция на отрезке
9. RMQ → LCA за O(n) (построение декартова дерева за O(n²) и O(n)), итого RMQ за [O(n), O(1)]
10. LCA в Offline за O((n+m)*) (алгоритм Ахо-Ульмана-Тарьяна)
11. Функция на пути в статичном дереве: online = двоичные подъёмы
12. Обратимая ассоциативная функция на пути в статичном дереве за [O(n), O(1)]