ЛКШ 2018, 3-й день, Больше структур данных Богу структур данных (Сергей Копелиович)

  1. Persistent: сборка мусора
    1. Задача: копирование памяти
    2. Варианты сборки: стек, список

  2. ETT = Euler-Tour-Tree (Acyclic Dynamic Connectivity Online)
    1. Подробно про реализацию, так как будет задача в контесте

  3. Link-Cut-Tree
    1. Expose, потенциал, logn вызовов split/merge
    2. MakeRoot, Link, Cut функция на пути

  4. Splay деревья
    1. Операция Splay, выражение через неё Split, Merge, Add, Del
    2. [skipped] Доказательство времени работы 3(log R(v) - log R(u)) + 1
    3. [skipped] Доказательство времени работы ∑ k(v) (log (m / k(v)) + 1)
    4. Использование в Link-Cut : суммарное время Expose = O(logn)

  5. Корневая
    1. split/rebuild, split/merge на примере reverse/insert
    2. отложенные операции (lazy propagation) на примере сортированного массива

  6. DCP Offline
    1. Удаления можно свести к добавлениям, получили решение с DSU за log2
    2. Корневая по запросам за O(m3/2)
    3. [skipped] DCP Offline за O(mlogm)

  7. [skipped] Дополнительно: ещё про деревья
    1. [skipped] HLD
    2. [skipped] Centroid (и минимум на пути за O(1))
    3. [skipped] Сливаемые множества

  8. [skipped] 2D-деревья
  9. [skipped] Мо