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

Лекции группы A0 - Лекция 09 - Минимумы + Квадродерево (Сергей Копелиович)

Краткий план лекции "Минимумы + Квадродерево"

1. Квадро-дерево (modify rectangle in O(sqrt(N))) time
2. Min на отрезке массива (за O(1))
3. Min на путях дерева (массив = частный случай дерева!) (за O(log*n) в offline)
4. Другие задачи про деревья

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

1. Квадро-дерево
1. На квадрате NxN запрос за O(n)
2. На плоскости есть N точек. O(NlogN) памяти, O(sqrt(N)) на запрос.
3. Квадро-дерево поддерживает операцию {+= на прямоугольнике}
2. Min на отрезке массива
1. Sparse table [O(nlogn), O(1)]
2. RMQ --> LCA --> RMQ+-1 --> [O(n), O(1)]
3. Offline метод в случае только увеличивающихся L и R : [O(n+m)]
4. Offline метод с СНМ : [O((n+m)*)]
3. Min на путях дерева (массив = частный случай дерева!)
1. Покрытие дерева путями: [O(n), O((logn)^2)], SplayTree=[O(n), O(logn)]
2. Двоичный подъем: [O(nlogn), O(logn]
3. Offline алгоритмы
1. Обход дерева dfs-ом от корня: знаем глубину + умеем прыгать => [O(n), O(logn)]
2. Подъем на 2^k из каждой вершины + Sparse table => [O(nlogn), O(1)]
3. Online версия Sparse Table = [O(nlogn), O(logn)]
4. Разбиваем дерево на слои, получаем дерево из O(n/logn) вершин => [O(n), O(logn)], [O(n), O(log*n)]
5. Метод с СНМ - реализация снизу [O(n), O(logn)]
6. Метод с СНМ - реализация cверху [O(n), O(logn)]
4. Другие задачи про деревья
1. Проверка - является ли остов минимальным [O(E)]
2. Рандомизированный алгоритм поиска MST [O(E)]