Функции на путях в дереве, MST за O(E) (4 марта)

  1. Offline
    1. LCA-Offline (алгоритм Тарьяна)
    2. Модификация (RMQ → LCA) + LCA-Offline = RMQ-Offline. Упрощение алгоритма.
    3. Ответ на запросы на путях дерева в Offline dfs-ом с деревом отрезков
  2. Ответ на запросы на путях неменяющегося дерева двоичными подъёмами
  3. Сумма на пути дерева в Online
    1. Случай, когда веса не меняется
    2. Случай, когда веса рёбер меняется
    3. Случай, когда веса вершин меняется (биекция вершин и рёбер)
  4. Минимум на путях дерева в Offline
    1. За O((m+n)logn)
    2. За O*(m+n)
    3. Проверка MST на минимальность за линейное время
  5. Рандомизированный алгоритм построения MST за линейное время
    1. Алгоритм = 3 шаги Борувки + построить от случайной половины рёбер + выкинуть F-тяжёлые + построить от оставшихся
    2. Лемма о количестве F-тяжёлых рёбер с доказательством
    3. Оценка времени в среднем O(n+m)
    4. [не успеем] Оценка времени в худшем min(O(n2), O((n+m)logn))