Кружок обучения мастерству программирования при СПбГУ

Лекции группы A0 - Лекция 05 - Еще кое-что про Деревья

Краткий план лекции на тему "Еще кое-что про Деревья"

1. Курсовая от Сени Смирнова
2. Изоморфизмы деревьев за O(nlogn), O(n)
3. LCA offline и online
4. Функции на путях дерева в offline и online
5. Геометрия, несколько offline алгоритмов

Полный план лекции

1. Курсовая от Сени Смирнова
2. Доказательство амортизационной оценки O(mlogn) на сжатие путей в СНМ
3. Изоморфизм деревьев и динамика по дереву
1. Для каждого ребра посчитать, S1 * S2 --- произведение размеров поддеревьев
2. Посчитать сумму длин всеx путей в дереве
3. Изоморфизм подвешенных деревьев за O(nlogn)
4. Изоморфизм подвешенных деревьев за O(n) с хэшами
5. Изоморфизм НЕ подвешенных деревьев за O(nlogn)
6. Для каждого ребра посчитать, суммарную длину путей, через него проходящих
4. Функция на пути дерева = LCA + функция на вертикальном пути
5. LCA, классические простые алгоритмы
1. LCA-Offline (Ахо-Ульман-Тарьян)
2. Сведение к дереву отрезков лево-праым обходом
3. Метод двоичных подъемов
6. Функции на путях дерева в offline
1. Сумма offline за [O(n), O(1)]
2. Минимум offline за [O(nlogn), O(logn)] (метод двоичного подъема)
3. Минимум offline за [O(n), O(logn)] (СНМ, подъем снизу вверх)
7. Функции на путях дерева в online
1. Сумма online за [O(n), O(logn)] (дерево отрезков с +-1)
2. Минимум online за [O(n), O((logn)^2)] (покрытие путями, путь = дерево отрезков)
3. Минимум online за [O(nlogn), O((logn)^2)] (время входа-выхода => 2D дерево отрезков)
4. Минимум online амортизационно за O(mlogn) - применяем Splay-tree
8. Offline методы в геометрии - ScanLine
1. K точек. Определить, где они находятся, относительно невыпуклого N-угольника за O(NlogN + KlogK).
2. В случае выпуклого O(N + KlogK)
3. Поиск экстремальных точек для K прямых и выпуклого N-угольника за O(N + KlogK)
4. Для невыпуклого = построить выпуклую оболочку