В 2022 году Computer Science Center приостановил набор и обучение
Курсы
/
Дополнительные главы алгоритмов, часть 1
/
осень 2021
/

Лекция 4. LCA и RMQ

Четверг, 30 сентября 2021
Таймс, 2 этаж, ауд.204
Список тем / 25 записей
    1.
    Лекция 1. Куча
    2.
    Семинар 1. Куча
    3.
    Семинар 2. Дерево отрезков
    4.
    Лекция 2. Дерево отрезков
    5.
    Лекция 3. Дерево поиска
    6.
    Семинар 3. Дерево поиска
    7.
    Лекция 4. LCA и RMQ
    8.
    Семинар 4. LCA и RMQ
    9.
    Лекция 5. HLD и link-cut tree
    10.
    Семинар 5. HLD и link-cut tree
    11.
    Лекция 6. Центроидная декомпозиция
    12.
    Семинар 6. Центроидная декомпозиция
    13.
    Лекция 7. Теория чисел
    14.
    Лекция 8. Euler Tour Tree и динамическая связность
    15.
    Семинар 8. Разбор домашних заданий по центроидной декомпозиция и теории чисел
    16.
    Лекция 9. Scapegoat Tree
    17.
    Семинар 9. Scapegoat Tree
    18.
    Лекция 10. Персистентные структуры данных
    19.
    Семинар 10. Персистентные структуры данных
    20.
    Лекция 11. Алгоритмы во внешней памяти
    21.
    Семинар 11. Алгоритмы во внешней памяти
    22.
    Лекция 12. Cache-oblivious алгоритмы
    23.
    Семинар 12. Cache-oblivious алгоритмы
    24.
    Лекция 13. Параллельные алгоритмы
    25.
    Семинар 13. Параллельные алгоритмы

Описание

  1. Задача LCA поиска нижайшего общего предка двух вершин в подвешенном дереве. Решение с \(\mathcal O(n\log n)\) препроцессинга и памяти, \(\mathcal O(1)\) на запрос: двоичные подъёмы.

  2. Задача RMQ поиска минимума на подотрезках массива. Сведение LCA к RMQ за \(\mathcal O(n)\): эйлеров обход.

  3. LCA и RMQ с \(\mathcal O(n)\) препроцессинга и памяти, \(\mathcal O(\log n)\) на запрос: дерево отрезков.

  4. LCA и RMQ с \(\mathcal O(n\log n)\) препроцессинга и памяти, \(\mathcal O(1)\) на запрос: разреженная таблица.

  5. LCA и частный случай RMQ с \(\mathcal O(n)\) препроцессинга и памяти, \(\mathcal O(1)\) на запрос: алгоритм Фараха-Колтона, Бендера.