748
правок
Изменения
→4 Задача о наименьшем общем предке
# [[Сведение задачи LCA к задаче RMQ]]
# [[Сведение задачи RMQ к задаче LCA]]
# взяли [[Метод двоичного подъема]] 3## добавить пример работы алгоритма
# [[Решение RMQ с помощью разреженной таблицы]]
# [[Двумерная разреженная таблица]]
# [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)
# [[Алгоритм Хьюи]]
# взяли [[Heavy-light декомпозиция]] 6## "решается с помощью heavy-light декомпозиции" — может быть решена## "Пусть A, B - ко" — дефисы нужно заменить на тире## В начале у тебя идут вершины a,b и A,B, а потом u,v и a,b. Надо сделать единообразно, чтобы начало конспекта и его конец согласовывались. Например, сделать корни путей большими буквами — норм. Тогда можно либо a,b и A,B, либо u,v и U,V.## "В данном случае корень одного из путей является вершиной другого." — а почему пути не могут пересекаться крест-на-крест?## Слишком много повтором «Пусть» в доказательстве леммы.## "Но LCA должен принадлежать двум путям. Но" — дублирование «Но»## "Предположим, что LCA не равны" — криво написано, нужно формально исходя из формулировки## Ну и вообще, как будто слов пожадничал на лемму и кое-как написал## "Построим декомпозицию." — декомпозицию чего и для чего? Очень плохо оставлять открытый контекст, особенно в начале пункта. Лучше чуть более подробно описать, чтобы было понятно## "Корень пути, на котором лежит текущая вершина.## Из всех путей выбираем тот, чья начальная вершина наиболее удалена от корня дерева." — вообще непонятно, как связано то, что мы хотим сохранить с тем, что написано потом. Нет предложения-связки## "Пусть требуется" — опять пуст## "Пусть на данной итерации" — как будто других слов нет## "LCA будет та" — это не по-русски## Возьми LCA в тексте везде в \mathrm## "Потому что бесконечно большое количество путей" — откуда в конечном дереве взялось бесконечно большое число путей?
# [[Алгоритм Шибера-Вишкина]]<tex>^\star</tex>
# взяли [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]<tex>^\star</tex> 0,25## См. также
# [[Link-Cut Tree]]<tex>^\star</tex>
# взяли [[Rake-Compress деревья]]<tex>^\star</tex> 0,25## Английские термины
