Я пытался понять, как работает подход LCA Sparse Table, и искал доказательство правильности алгоритма. Но, к сожалению, я не мог легко найти его в Интернете. Поэтому я решил написать один.
Сначала я определю проблему. Проблема гласит, что в дереве u и v есть два узла. Вы должны найти наименьшего общего предка из двух. Для этого мы предварительно вычисляем двумерный массив P[i][j], в котором хранится номер узла. из 2, возведенных в степень j-го предка узла i.
Теперь алгоритм можно увидеть на сайте топового кодера https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/
Я постараюсь выяснить на более высоком уровне, какие шаги мы пытаемся сделать.
Сначала мы меняем местами два узла так, чтобы узел p находился на большей глубине, чем узел q. Чтобы нам не пришлось писать код для обоих случаев.
Во-вторых, мы вычисляем бревно большей глубины.
Затем мы пытаемся переместить указатель p на уровень, который совпадает с q.
Теперь наступает самая важная часть, которую я попытаюсь объяснить на примере.
Предположим, что глубина p равна 17, а глубина q равна 7, мы пытаемся уменьшить глубину в степени двойки.
В нашем случае значение log будет равно 4.
Сначала мы попытаемся уменьшить глубину на 16, что сделает глубину p равной 1, что невозможно.
Затем мы пытаемся уменьшить глубину на 8, что уменьшит глубину p с 17 до 9, что эквивалентно перемещению узла на глубине 17 к его предку на глубине 9, поэтому мы назначим p с P[p] [3]
Затем мы пытаемся уменьшить на 4, что также невозможно, так как уменьшает глубину p до 5, но мы хотим 7
Затем, наконец, мы пытаемся уменьшить на 2, что делает нашу глубину равной 7, поэтому мы присваиваем p значение P[p] [1], и все готово.
Теперь мы проверяем, равно ли p равно q, если да, то мы нашли нашего низшего общего предка, которым является p
Если p не равно q, то теперь оба имеют одинаковую глубину, что мы делаем сейчас: мы уменьшаем глубину, сдвигая ее к ее предку, так что предок, который мы сдвигаем, не одинаков для обоих, позвольте мне рассмотреть пример. Я предполагаю, что LCA на глубине 3 от узла
Мы пытаемся уменьшить глубину на
16, что невозможно, так как 7–16 ‹ 0
Пробуем уменьшить на 8, что тоже неосуществимо
Мы пытаемся уменьшить на 4, что сдвигает и p, и q на 3, но 3-й предок равен, поэтому мы отбросим этот сдвиг.
Теперь мы пытаемся уменьшить глубину на 2, что берет их обоих на уровне 5, а предки уровня 5 не равны, мы сдвигаем
Затем мы пытаемся уменьшить 5 на 1, что также возможно, поэтому теперь у нас есть p и q на глубине 4.
Теперь нашим ответом будет первый родитель p и q
Теперь, почему все это работает
Все это работает, потому что каждое число может быть выражено как сумма степеней двойки.
Теперь посмотрим, как это сыграло свою роль 17 - 7 = 10 = 8 + 2
Таким образом, мы могли бы сдвинуться сначала на 8, а затем на 2, чтобы достичь желаемой глубины.
Аналогично было, когда мы пытались уменьшить с 7 до 3.
Надеюсь, это объяснение поможет вам понять концепцию LCA.