Я пытался понять, как работает подход 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.