Изменения

Перейти к: навигация, поиск

Алгоритмы и структуры данных2:Тикеты

33 байта добавлено, 13:44, 22 апреля 2018
4 Задача о наименьшем общем предке
# [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)
# [[Алгоритм Хьюи]]
# взяли [[Heavy-light декомпозиция]] 6
## "решается с помощью heavy-light декомпозиции" — может быть решена
## "Пусть A, B - ко" — дефисы нужно заменить на тире
## "Потому что бесконечно большое количество путей" — откуда в конечном дереве взялось бесконечно большое число путей?
# [[Алгоритм Шибера-Вишкина]]<tex>^\star</tex>
# взяли [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]<tex>^\star</tex> 0,25
## См. также
# [[Link-Cut Tree]]<tex>^\star</tex>
# взяли [[Rake-Compress деревья]]<tex>^\star</tex> 0,25
## Английские термины

Навигация