HLD, Link-Cut, линейное MST (24 мая 2017)

  1. [15 минут] Heavy-Light decomposition
    1. Идея: разбиение дерево на пути, каждая вершина ровно в одном пути.
    2. Лемма про число прыжков: на любом пути к корню не более log2n прыжков между путями.
    3. Тонкости реализации (как создать HLD, как прыгать по ней вверх, как считать функцию на пути без LCA)
    4. Общая идея решения задач: сперва решить на отрезке массива деревом отрезков или BST, затем обобщить до путей на дереве, добавив HLD
    5. Признаки задачи, к которым применимо HLD: задача про дерево, в дереве меняются веса вершин/рёбер
  2. [30 минут] Link-Cut-Tree
    1. Идея: динамическое разбиение вершин корневого дерева на пути. База: каждая вершина − самостоятельный путь.
    2. Операция Expose, время работы k*logn.
    3. Амортизированное оценка на k = O(logn). Потенциал − число тяжелых рёбер, покрытых путями.
    4. Операция MakeRoot. Изменение потенциала − не более чем число лёгких рёбер на пути, то есть, O(logn)
    5. Функция на пути дерева; link(a,b), cut(a,b): MakeRoot(a) + MakeRoot(b) + O(1)
    6. Сравнение с Euler-Tour-Tree: кроме link и cut умеет считать функцию на пути, находить lca
− Перерыв −
  1. [35 минут] MST за линейное время
    1. Проверка MST на минимальность за линейное время (ссылаемся на RMQ за O(1), которым на самом деле не владеем)
    2. Алгоритм = 3 шаги Борувки + построить остов F от случайной половины рёбер + выкинуть F-тяжёлые + построить от оставшихся
    3. Лемма о количестве F-тяжёлых рёбер с доказательством: (n - 1)(1/p - 1)
    4. Оценка времени в среднем O(n+m)
  2. [13 минут] (RMQ → LCA) + LCA-Offline = RMQ-Offline за O((n+m)α). Только если останется время!
    1. Предподсчитали за линию вектора ListOfLeftBorders[R]. Перебираем запросы по возрастанию Ri.
    2. При фиксированном Ri отрезок [1..Ri] разбивается на [1..Min1] (Min1..Min2] (Min2..Min3) и т.д. При этом a[Min1] ≤ a[Min2] ≤ a[Min3] и т.д.
    3. Если Lj лежит в (Mini..Mini+1], то ответ для запроса Min[Lj..Rj] равен a[Mini+1]
    4. Реализация: минимумы лежат в стеке, мы отрезки (Mini..Mini+1] в СНМ. Добавляя a[R], снимаем вершину стека, объединяем соответствующие множества.