RMQ & LCA

    Соц.опрос: языки программирования С/C++, Java, Python, Pascal

  1. [05] [Сережа.K] С/C++: структура с битовым сжатием
  2. [10] [Ваня] RMQ деревом отрезков за [n, logn] (минимум на отрезке, изменение в точке, реализация сверху)
  3. [10] [Ваня] RMQ через sparse table за [nlogn, 1]
  4. [05] [Ваня] Проверка, является одна вершина предком другой за O(1)
  5. [17] [Ваня] Двоичные подъемы: LCA за [nlogn, logn] (двумя способами)
  6. [---] [Ваня] Упражнение: посчитать двоичными подъемами глубину вершины за logn
  7. [15] [Ваня] LCA → RMQ±1 (Эйлеров обход дерева)
  8. [03] [Ваня] LCA мы теперь тоже умеем за [nlogn, 1] (LCA → RMQ, sparse table)

    9. Перерыв

  9. [20] [Сережа.K] RMQ → LCA (строим декартово дерево)
  10. [05] [Сережа.K] LCA в Offline за O((n+m)*) (алгоритм Ахо-Ульмана-Тарьяна)
  11. [05] [Сережа.K] минимум на пути в дереве в Online: двоичные подъемы [nlogn, logn]
  12. [05] [Сережа.K] Sparse table за [n, logn]
  13. [05] [Сережа.K] Sparse table за [n, log*n] (рекурсивное замыкание предыдущей идеи)
  14. [10] [Сережа.K] Фарах-Колтон-Бендер: RMQ → LCA → RMQ±1 и алгоритм 4-х русских для решения последней