ЛКШ 2018, 1-й день, LCA, RMQ, LA, Euler-Tour (Сергей Копелиович)

  1. LCA, RMQ: простое
    1. LCA двоичными подъёмами: два способа; проверка "является ли предком"
    2. RMQ разреженными таблицами: [nlogn, 1]

  2. LCA, RMQ: возможно, новое
    1. Улучшаем sparse table до [nloglogn, 1] и [n, loglogn], рекурсивно замыкаем
    2. Решение RMQ±1 за [n, 1] четырьмя русскими
    3. RMQ → LCA → RMQ±1 (Построение Декартового дерева, Эйлеров обход)
    4. Другое использование Эйлерова обхода: функция от поддерева

  3. LA
    1. LA.Offline
    2. LA.Online [O(n), O(logn)] − алгоритм Вишкина
    3. LA.Online [O(nlogn), O(1)] − лестничная декомпозиция
    4. [skipped] LA.Online [O(n), O(1)] − добавляем эйлеров обход и 4 русских
− Перерыв −
  1. LCA: алгоритм Тарьяна.

  2. Дерево отрезков снизу
    1. Описание, запросы get, change
    2. Сравнение с реализацией сверху

  3. Задачи
    1. += на отрезке через сумму на отрезке
    2. Сумма на пути дерева = префиксные суммы
    3. Сумма на пути, изменение в ребре = эйлеров обход, рёбра с разными знаками
    4. Сумма на пути, изменение в вершине = два эйлеровых обхода (по времени входа, по времени выхода)
    5. Биекция между вершинами и рёбрами
    6. Сумма на пути, += на пути : все пути во всех запросах до корня
    7. Минимум на пути в дереве без изменений в offline : через сортировку рёбер и СНМ
    8. Минимум на пути в дереве без изменений в offline : через сортировку запросов и СНМ

  4. [skipped] Дополнительное
    1. [skipped] RMQ.Offline: напрямую без RMQ → LCA
    2. [skipped] Disjoint Sparse Table
    3. [skipped] Задача: даны два подвешенных дерева, номера вершин различны, запрос − найти размер пересечения двух поддеревьев