Heavy-Light декомпозиция

Понедельник, 23 февраля 2015

Таймс, ауд. 404

Описание

Поиск минимума на пути в дереве
Статическая задача: двоичные подъемы
Тяжелые и легкие ребра
Разбиение на тяжелые пути
Оценка \(log(n)\) на число легких ребер
Финальная оценка \(log^2(n)\)
Off-topic: амортизационный анализ
- амортизационное время. определение
- метод потенциалов
- метод предоплаты