Что: Лекция
Когда: Четверг, 09 марта 2017, 18:30–19:50
Где: Таймс, ауд. с чёрными досками

Описание

  • Sparse-Table: RMQ за [O(nlogn), O(1)], за [O(n), O(loglogn)], за [O(nloglogn), O(1)]

  • Двоичные подъёмы: LCA, минимум на пути

  • Эйлеров Обход: LCA -> RMQ, функция на поддереве

  • Фарах-Колтон-Бендер: LCA -> RMQ±1; RMQ и LCA за [O(n), O(1)]