Link-Cut tree
Основа
- Покрытие дерева путями
- Хранение пути в виде декартова дерева
- Сделать вершину корнем
- Ответ на запрос "функция на пути от v до корня" за O(klogn), где k число прыжков
Link-Cut
- Expose
- MakeRoot
- Link
- Cut
- Get(a, b)
Подробная реализация
- Что нам нужно от декаротва дерева?
- Как мы делаем Expose?
- Как мы делаем MakeRoot
Доказательство корректности
- Потенциал = количество тяжёлых рёбер, покрытых путями
- Изменение потенциала при Expose
- Изменение потенциала при Reverse
- Изменение потенциала при Link и Cut
Splay-Tree
- Splay
- Теорема про время работы без доказательства
- Соединяем с Link-Cut tree