Бинарный лифтинг и его приложения

Древовидная структура данных — одна из самых интересных структур данных в информатике. На основе этой структуры данных можно сформулировать множество интересных задач. Сегодня мы обсудим одну из таких интересных задач. Вот как можно определить проблему -

Имея корневое дерево с n узлами, вы должны ответить на q запросов. В каждом запросе вы должны найти k^го предка узла.

Давайте сначала обсудим простое решение. Для каждого запроса мы перебираем всех предков данного узла. Мы возвращаем требуемый узел-предок. Вот псевдо реализация.

```питон

defsolveQuery(узел, k):

пока к>0:

к--;

узел = родитель[узел];

возвратный узел;

Хотя реализация проста, временная сложность в наихудшем случае составляет «O(N.Q)». Таким образом, решение не будет работать, когда квадратичная реализация слишком дорога. Вот где на сцену выходит бинарный лифтинг. Это интересная идея решения той же проблемы в O(log(N).Q).

Мотивация для бинарного подъема

С нашей неудачной попыткой эффективно решить проблему мы можем почувствовать потребность в некоторой предварительной обработке. Предварительная обработка, которую мы выполняем, должна помочь нам быстро ответить на каждый запрос. Главный вопрос заключается в том, какая предварительная обработка нужна проблеме?

:::Информация

Предварительная обработка — это процесс выполнения (некоторых) вычислений заранее, чтобы обеспечить более качественную и эффективную обработку каждого запроса. Некоторые метаданные поддерживаются как часть этого процесса, который используется при ответах на фактические запросы.

Давайте подумаем об этом. В настоящее время мы знаем для каждого узла его родителя. Таким образом, из любого узла мы можем найти только «1 ^ st» предка узла за постоянное время. Таким образом, когда мы сталкиваемся с проблемой поиска "k^th" предка, мы вынуждены сделать как минимум "k" прыжков. Другими словами, мы представляем «k» как «1 + 1 + … + 1», где «1» встречается «k» раз. Итак, что, если мы можем найти любого (2 ^ x)th родителя узла за постоянное время? Конечно, мы можем представить «k» как сумму степеней «2». Поскольку k может быть не более n, мы всегда можем представить k как сумму элементов log(n). Таким образом, ответ на каждый запрос теперь занимает O(log(n)) времени.

Таким образом, если мы сможем эффективно выполнить предварительную обработку, общая временная сложность составит «O(PP + Q.log(N))».

Актуальный алгоритм бинарного подъема

Весь процесс бинарного подъема разделен на две части: (1) предварительная обработка и (2) разрешение запроса. Мы обсудим их в следующих подразделах.

Предварительная обработка

В соответствии с идеями, обсуждаемыми в разделе мотивации, нам нужно будет хранить (2^x)th предка для каждого узла. Сохраним эту информацию в таблице предок. Размеры этой таблицы равны n*log(n). Вот что представляет собой каждая запись в этой таблице:

предок[n][x] -> (2^x)-й родитель узла n

Обратите внимание, что поскольку первый предок любого узла является его собственным родителем, мы можем написать ancestor[n][0] = parent[n] для каждого узла n. Теперь, чтобы заполнить оставшиеся записи, мы можем следовать следующему рекурсивному соотношению:

предок[n][x] = предок[предок[n][x-1]][x-1]

Идея, с помощью которой мы можем прийти к приведенному выше соотношению, заключается в следующем: чтобы достичь предка (2^x)th, мы можем сделать два прыжка на размер (2^(x-1)). Поскольку (2^(x-1)) + (2^(x-1)) = (2^(x)), мы в конечном итоге достигнем требуемого предка. Таким образом, у нас есть все необходимые знания для выполнения этапа предварительной обработки. Вот псевдо реализация.

```javascript

для узла в [0:n-1]:

предок [узел] [0] = родитель [узел]

// Мы не можем подняться от корня

для x в [1: log (n)]:

предок [корень] [x] = корень

для x в [1: log (n)]:

для узла в [0:n-1]:

если узел является корневым, продолжайте

предок[узел][x] = предок[предок[узел][x-1]][x-1]

Разрешение запроса

После того, как мы завершили часть предварительной обработки, мы можем эффективно ответить на каждый запрос. Идея такая же, как обсуждалась в разделе мотивации, мы представим k как сумму степеней двойки. Затем мы будем двигаться вверх по дереву, следуя этим степеням двойки. Приведенный ниже псевдокод выражает эту идею более кратко.

```javascript

defsolveQuery(узел,k):

для я в [31:0]:

if k & (1< 0: // Проверяем, присутствует ли 2^i в двоичном представлении k

node = ancestor[node][i] // Перейти к (2^i)-ому предку

узел возврата

Реализация бинарного подъема

:::Информация

В приведенном ниже коде предполагается, что дерево состоит из n узлов от 0 до n-1. Поскольку дерево с n узлами имеет n-1 ребер, входные данные предоставляют эти n-1 ребер в формате от родительского к дочернему. Дерево укоренено в 0.

```нажмите

include <бит/stdc++.h>

использование пространства имен std;

родитель vector;

предок vector>;

интервал основной () {

инт н; цин>>н; // n — количество узлов с номерами от 0 до n-1

int LOG = log2 (n);

родитель.назначить(n, 0);

предок.назначить(n, вектор(LOG+2));

// Предполагая, что узел 0 является корнем дерева

родитель[0] = 0;

// Предполагая, что следующие n-1 строк содержат ребра в формате: parent_node child_node

for(int i=0; i<n-1; ++i) {

инт р, с; цин>>р>>с;

родитель [с] = р;

for(int i=0; i<n; ++i) ancestor[i][0] = parent[i];

for(int x=1; x<=LOG+1; ++x) ancestor[0][x] = 0;

for(int x=1; x<=LOG+1; ++x) {

for(int i=0; i<n; ++i) {

предок[i][x] = предок[предок[i][x-1]][x-1];

интервал д; цин>>q; // Количество запросов

в то время как (q--) {

инт узел, к; цин>>узел>>к;

for(int i=LOG+1; i>=0; i--) {

if( k & (1<<i) ) узел = предок[узел][i];

cout<<узел<<endl;

Наименьший общий предок (LCA) — применение бинарного подъема

Разобравшись с интересными идеями бинарного лифтинга, мы можем сосредоточить внимание на некоторых его интересных применениях. Одним из таких приложений является поиск [наименьшего общего предка] (https://en.wikipedia.org/wiki/Lowest_common_ancestor) заданной пары узлов в дереве. Кроме того, предположим, что таких запросов может быть Q. Удивительно, но мы можем использовать процесс бинарного подъема для довольно элегантного решения этой задачи.

Начнем с описания алгоритма. Затем мы увидим, где бинарный лифтинг вступает в игру.

1. == Нам даны два узла, и мы говорим, что n1 и n2 являются указателями на эти узлы. Мы должны найти их LCA. ==

1. ==Перемещайте вверх указатель, указывающий на узел на большей глубине (самый дальний от корня), пока глубины обоих узлов не станут равными.==

1. == Если и n1, и n2 указывают на один и тот же узел, указанный узел является LCA. Мы возвращаем этот узел и завершаем работу. В противном случае мы переходим к шагу 4. ==

1. == Мы продвигаем оба указателя узла вверх по дереву до тех пор, пока их больше нельзя будет перемещать, не указывая на один и тот же узел. ==

1. == Верните родителя узла, на который указывает n1, в качестве LCA. ==

Алгоритм довольно прост, и наивная реализация потребует O (n) времени, чтобы вернуть LCA. Однако загвоздка в этом алгоритме заключается в том, что мы можем использовать двоичный подъем для ускорения шагов 2 и 4. Сначала мы посмотрим, как он вписывается в шаг 2.

Учтите, что указатель узла n1 указывает на узел на большей глубине, если не поменять местами n1 и n2. Теперь, согласно шагу 2, нам нужно переместить указатель узла «n1» вверх, пока глубина вновь указанного узла не станет равной глубине узла, на который указывает «n2». Мы можем рассматривать это как нахождение [depth(n1)-depth(n2)]th предка узла, на который указывает n1. Это решается за логарифмическое время с помощью бинарного подъема.

Теперь переходим к шагу 4. Достигнув шага 4, мы уверены, что узлы, на которые указывают «n1» и «n2», различны. Мы должны одновременно перемещать вверх оба указателя узлов, следя за тем, чтобы они не указывали на один и тот же узел. Следующий фрагмент кода описывает, как мы можем использовать двоичный подъем для выполнения этого шага.

n1, n2 <- указатели узлов

for (int i=log(n); i>=0; i--) {

если(предок[n1][i]!=предок[n2][i]) {

n1 = предок[n1][i];

n2 = предок[n2][i];

вернуть parent[n1] как LCA

Заключительные замечания

На этом удивительный процесс бинарного лифтинга завершен. Часто удивительно, как простые идеи могут быть использованы для решения проблем большой сложности. Мы обсудили одно из многих применений бинарного подъема, то есть младший общий предок (LCA). Можете ли вы выяснить какие-либо другие? Дайте мне знать в разделе комментариев😊.

Вы можете следить за мной в Твиттере по адресу @rrriiss03. Следите за новыми интересными статьями.