RMQ, LCA

Четверг, 25 февраля 2016
Таймс, ауд. 404

Описание

  • 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)]