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

  1. [15 минут] (RMQ → LCA) + LCA-Offline = RMQ-Offline.
  2. [15 минут] Сумма на пути дерева в Online
    1. Случай, когда веса не меняется
    2. Случай, когда веса рёбер меняются
    3. Случай, когда веса вершин меняются (биекция вершин и рёбер)
  3. [25 минут] MST за линейное время
    1. Проверка MST на минимальность за линейное время
    2. Алгоритм = 3 шаги Борувки + построить от случайной половины рёбер + выкинуть F-тяжёлые + построить от оставшихся
    3. Лемма о количестве F-тяжёлых рёбер с доказательством: (n - 1)(1/p - 1)
    4. Оценка времени в среднем O(n+m)
    5. Оценка времени в худшем min(O(n2), O((n+m)logn))
--- Перерыв ---
  1. [30 минут] Минимум на путях дерева, веса не меняются
    1. Существующие online решения
      1. Сentroid decomposition за O(m + nlogn)
      2. Двоичные поъёмы за O(mlogn + n)
    2. Offline решения
      1. dfs + дерево отрезков за O((m+n)logn)
      2. Со сжатием путей за O((m+n)logn). На практике рулит.
      3. Попытка добавить ранговую эвристику, чтобы было O((m+n)α)