Рубрики

Тяжелое Легкое Разложение | Набор 2 (реализация)

Мы настоятельно рекомендуем ссылаться на этот пост ниже.

Тяжелое Легкое Разложение | Комплект 1 (Введение)

В вышеприведенном посте мы обсуждали разложение Heavy-Light (HLD) с помощью приведенного ниже примера.

Предположим, у нас есть несбалансированное дерево (не обязательно двоичное дерево) из n узлов , и мы должны выполнить операции над деревом, чтобы ответить на несколько запросов, каждый из которых может быть одного из двух типов:

  1. изменение (a, b) : обновить вес a- го ребра до b.
  2. maxEdge (a, b) : вывести максимальный вес ребра на пути от узла a к узлу b. Например, maxEdge (5, 10) должен вывести 25.

В этой статье обсуждается реализация того же

Наша линия атаки для этой проблемы:

  1. Создание дерева
  2. Настройка размера, глубины и родительского поддерева для каждого узла (с использованием DFS)
  3. Разложение дерева на непересекающиеся цепочки
  4. Построение дерева сегментов
  5. Отвечая на вопросы

1. Создание дерева. Реализация использует матричное представление дерева смежности для простоты понимания. Можно использовать rep списка смежности с некоторыми изменениями в источнике. Если число ребер e с весом w существует между узлами u и v, мы будем хранить e в tree [u] [v] и tree [v] [u], а вес w — в отдельном линейном массиве весов ребер (n- 1 ребра).

2. Настройка размера, глубины и родительского поддерева для каждого узла. Затем мы выполняем DFS для дерева, чтобы настроить массивы, в которых хранятся родительский размер, размер поддерева и глубина каждого узла. Еще одна важная вещь, которую мы делаем во время DFS, — это сохранение более глубокого узла каждого ребра, которое мы пересекаем. Это поможет нам во время обновления дерева (запрос change ()).

3 и 4. Разложение дерева на непересекающиеся цепочки и построение дерева сегментов Теперь начинается самая важная часть: HLD. Когда мы пересекаем ребра и достигаем узлов (начиная с корня), мы помещаем ребро в основание дерева сегментов, мы решаем, будет ли узел направлен в новую цепочку (если это обычный дочерний элемент) или будет текущий расширение цепочки (специальный дочерний), хранить идентификатор цепочки, к которой принадлежит узел, и сохранять его место в базе дерева сегментов (для будущих запросов). Основа для дерева сегментов построена так, что все ребра, принадлежащие одной и той же цепочке, находятся вместе, а цепочки разделены светлыми ребрами.

Иллюстрация: мы начинаем с узла 1. Поскольку к этому узлу не было какого-либо ребра, мы вставляем «-1» в качестве веса воображаемого ребра в массив, который будет служить основой для дерева сегментов.
Затем мы переходим к специальному дочернему узлу 1, который является узлом 2, и, поскольку мы пересекали ребро с весом 13, мы добавляем 13 в наш базовый массив. Специальный дочерний узел узла 2 — это узел 6. Мы пересекаем ребро с весом 25, чтобы достичь узла 6. Вставляем в базовый массив. И аналогичным образом мы расширяем эту цепочку, пока не достигли конечного узла (в нашем случае — узла 10).
Затем мы переключаемся на обычного потомка родителя последнего конечного узла и отмечаем начало новой цепочки. Родитель здесь — это узел 8, а обычный потомок — это узел 11. Мы пересекаем ребро с весом 6 и вставляем его в базовый массив. Вот так мы завершаем базовый массив для дерева сегментов.
Также помните, что нам нужно хранить положение каждого узла в сегментном дереве для будущих запросов. Положение узла 1 равно 1, узел 2 равен 2, узел 6 равен 3, узел 8 равен 4,…, узел 11 равен 6, узел 5 равен 7, узел 9 равен 10, узел 4 равен 11 (индексирование на основе 1).

5. Отвечая на вопросы

Мы подробно обсудили запрос mexEdge () в предыдущем посте . Для maxEdge (u, v) мы находим максимальное весовое ребро на пути от u к LCA и v к LCA и возвращаем максимум два.

Для запроса change () мы можем обновить дерево сегментов, используя более глубокий конец ребра, вес которого нужно обновить. Мы найдем позицию более глубокого конца ребра в массиве, выступающего в качестве основы для дерева сегментов, а затем начнем наше обновление с этого узла и переместимся вверх, обновляя дерево сегментов. Скажем, мы хотим обновить ребро 8 (между узлом 7 и узлом 9) до 28. Положение более глубокого узла 9 в базовом массиве равно 10, мы делаем это следующим образом:

Ниже приведена реализация вышеописанных шагов в C ++.

   
/ * C ++ программа для разветвления Heavy-Light дерева * /
#include<bits/stdc++.h>

using namespace std;

  
#define N 1024

  

int tree[N][N];  // Матрица, представляющая дерево

  
/ * структура узла дерева. Каждый узел имеет родителя, глубину,

   размер поддерева, цепочка, к которой он принадлежит, и позиция

   в базовом массиве * /

struct treeNode

{

    int par;   // Родитель этого узла

    int depth; // Глубина этого узла

    int size; // Размер поддерева, укорененного в этом узле

    int pos_segbase; // Положение в базе дерева сегментов

    int chain;

} node[N];

  
/ * каждый край имеет вес и два конца. Мы храним более глубокий конец * /

struct Edge

{

    int weight;  // Вес ребра

    int deeper_end; // Более глубокий конец

} edge[N];

  
/ * строим одно дерево сегментов, на базовом массиве * /

struct segmentTree

{

    int base_array[N], tree[6*N];

} s;

  
// Функция добавления ребер в матрицу дерева
// e это Edge ID, u и v два узла, w это вес

void addEdge(int e, int u, int v, int w)

{

    / * дерево как неориентированный граф * /

    tree[u-1][v-1] = e-1;

    tree[v-1][u-1] = e-1;

  

    edge[e-1].weight = w;

}

  
// Рекурсивная функция для DFS на дереве
// curr - текущий узел, prev - родительский элемент curr,
// dep - это глубина

void dfs(int curr, int prev, int dep, int n)

{

    / * установить родителя текущего узла на предшественника * /

    node[curr].par = prev;

    node[curr].depth = dep;

    node[curr].size = 1;

  

    / * для каждого дочернего узла * /

    for (int j=0; j<n; j++)

    {

        if (j!=curr && j!=node[curr].par && tree[curr][j]!=-1)

        {

            / * установить более глубокий конец Edge как этот потомок * /

            edge[tree[curr][j]].deeper_end = j;

  

            / * сделать DFS на поддереве * /

            dfs(j, curr, dep+1, n);

  

            / * обновить размер поддерева * /

            node[curr].size+=node[j].size;

        }

     }

}

  
// Рекурсивная функция, разлагающая дерево на цепочки

void hld(int curr_node, int id, int *edge_counted, int *curr_chain,

         int n, int chain_heads[])

{

    / * если в текущей цепочке нет заголовка, этот узел является первым узлом

     * а также головка цепи * /

    if (chain_heads[*curr_chain]==-1)

        chain_heads[*curr_chain] = curr_node;

  

    / * установить идентификатор цепочки, к которой принадлежит узел * /

    node[curr_node].chain = *curr_chain;

  

    / * установить положение узла в массиве, выступающего в качестве основы для

       дерево сегментов * /

    node[curr_node].pos_segbase = *edge_counted;

  

    / * обновить массив, который является базой для дерева сегментов * /

    s.base_array[(*edge_counted)++] = edge[id].weight;

  

    / * Найти особенного ребенка (ребенка с максимальным размером) * /

    int spcl_chld = -1, spcl_edg_id;

    for (int j=0; j<n; j++)

      if (j!=curr_node && j!=node[curr_node].par && tree[curr_node][j]!=-1)

        if (spcl_chld==-1 || node[spcl_chld].size < node[j].size)

           spcl_chld = j, spcl_edg_id = tree[curr_node][j];

  

    / * если найден специальный ребенок, растянуть цепь * /

    if (spcl_chld!=-1)

      hld(spcl_chld, spcl_edg_id, edge_counted, curr_chain, n, chain_heads);

  

    / * для каждого другого (нормального) ребенка, используйте HLD для дочернего поддерева как отдельное

       цепь * /

    for (int j=0; j<n; j++)

    {

      if (j!=curr_node && j!=node[curr_node].par &&

            j!=spcl_chld && tree[curr_node][j]!=-1)

      {

        (*curr_chain)++;

        hld(j, tree[curr_node][j], edge_counted, curr_chain, n, chain_heads);

      }

    }

}

  
// Рекурсивная функция, которая создает дерево сегментов для массива [ss..se).
// si - индекс текущего узла в сегментном дереве st

int construct_ST(int ss, int se, int si)

{

    // Если в массиве есть один элемент, сохраняем его в текущем узле

    // сегментируем дерево и возвращаем

    if (ss == se-1)

    {

        s.tree[si] = s.base_array[ss];

        return s.base_array[ss];

    }

  

    // Если есть более одного элемента, то повторить для левого и

    // правильные поддеревья и храним минимум двух значений в этом узле

    int mid = (ss + se)/2;

    s.tree[si] =  max(construct_ST(ss, mid, si*2),

                      construct_ST(mid, se, si*2+1));

    return s.tree[si];

}

  
// Рекурсивная функция, которая обновляет дерево сегментов
// x - это узел, который нужно обновить до значения val
// si - начальный индекс дерева сегментов
// ss, se отмечаем углы диапазона, представленного si

int update_ST(int ss, int se, int si, int x, int val)

{

  

    if(ss > x || se <= x);

  

    else if(ss == x && ss == se-1)s.tree[si] = val;

  

    else

    {

        int mid = (ss + se)/2;

        s.tree[si] =  max(update_ST(ss, mid, si*2, x, val),

                         update_ST(mid, se, si*2+1, x, val));

    }

  

    return s.tree[si];

}

  
// Функция для обновления значения Edge e до val в сегментном дереве

void change(int e, int val, int n)

{

    update_ST(0, n, 1, node[edge[e].deeper_end].pos_segbase, val);

  

    // следующие строки кода не вносят изменений в наш случай, как мы

    // меняется в ST выше

    // Edge_weights [e] = val;

    // segtree_Edges_weights [deeper_end_of_edge [e]] = val;

}

  
// Функция для получения LCA узлов u и v

int LCA(int u, int v, int n)

{

    / * массив для хранения пути от вас к корню * /

    int LCA_aux[n+5];

  

    // Устанавливаем u более глубокий узел, если это не так

    if (node[u].depth < node[v].depth)

       swap(u, v);

  

    / * LCA_aux будет хранить путь от узла u к корню * /

    memset(LCA_aux, -1, sizeof(LCA_aux));

  

    while (u!=-1)

    {

        LCA_aux[u] = 1;

        u = node[u].par;

    }

  

    / * найти первый общий узел в пути от v к корню и u к

       root с использованием LCA_aux * /

    while (v)

    {

        if (LCA_aux[v]==1)break;

        v = node[v].par;

    }

  

    return v;

}

  
/ * Рекурсивная функция для получения минимального значения в заданном диапазоне

     индексов массива. Ниже приведены параметры для этой функции.

    st -> Указатель на дерево сегментов

    index -> Индекс текущего узла в дереве сегментов. Первоначально

              0 передается как root всегда с индексом 0

    ss & se -> Начальный и конечный индексы представленного сегмента

                  текущим узлом, т. е. st [index]

    qs & qe -> начальные и конечные индексы диапазона запросов * /

int RMQUtil(int ss, int se, int qs, int qe, int index)

{

    // printf ("% d,% d,% d,% d,% d / n", ss, se, qs, qe, index);

  

    // Если сегмент этого узла является частью заданного диапазона, возвращаем

    // мин отрезка

    if (qs <= ss && qe >= se-1)

        return s.tree[index];

  

    // Если сегмент этого узла находится за пределами указанного диапазона

    if (se-1 < qs || ss > qe)

        return -1;

  

    // Если часть этого сегмента перекрывается с заданным диапазоном

    int mid = (ss + se)/2;

    return max(RMQUtil(ss, mid, qs, qe, 2*index),

               RMQUtil(mid, se, qs, qe, 2*index+1));

}

  
// Возвращаем минимум элементов в диапазоне от индекса qs (начало запроса) до
// qe (конец запроса). В основном использует RMQUtil ()

int RMQ(int qs, int qe, int n)

{

    // Проверяем ошибочные входные значения

    if (qs < 0 || qe > n-1 || qs > qe)

    {

        printf("Invalid Input");

        return -1;

    }

  

    return RMQUtil(0, n, qs, qe, 1);

}

  
// Функция для перехода от u к v, отслеживая максимум
// мы перемещаемся на поверхность, меняя и цепи
// пока вы и v не принадлежите одному

int crawl_tree(int u, int v, int n, int chain_heads[])

{

    int chain_u, chain_v = node[v].chain, ans = 0;

  

    while (true)

    {

        chain_u = node[u].chain;

  

        / * если два узла принадлежат одной цепочке,

         * мы можем запросить между их позициями в массиве

         * действуя в качестве основы для дерева сегментов. После RMQ,

         * мы можем вырваться, потому что дальше идти некуда * /

        if (chain_u==chain_v)

        {

            if (u==v);   // тривиальным

            else

              ans = max(RMQ(node[v].pos_segbase+1, node[u].pos_segbase, n),

                        ans);

            break;

        }

  

        / * иначе мы запрашиваем между узлом u и заголовком цепочки, к которой

           ты принадлежишь, а потом меняешь на родителя главы цепочки

           к которому принадлежит u, указывая на изменение цепи * /

        else

        {

            ans = max(ans,

                      RMQ(node[chain_heads[chain_u]].pos_segbase,

                          node[u].pos_segbase, n));

  

            u = node[chain_heads[chain_u]].par;

        }

    }

  

    return ans;

}

  
// Функция для запроса MAX_EDGE

void maxEdge(int u, int v, int n, int chain_heads[])

{

    int lca = LCA(u, v, n);

    int ans = max(crawl_tree(u, lca, n, chain_heads),

                  crawl_tree(v, lca, n, chain_heads));

    printf("%d\n", ans);

}

  
// функция драйвера

int main()

{

    / * заполнить матрицу смежности -1, чтобы указать отсутствие соединений * /

    memset(tree, -1, sizeof(tree));

  

    int n = 11;

  

    / * аргументы в порядке: идентификатор ребра, узел u, узел v, вес w * /

    addEdge(1, 1, 2, 13);

    addEdge(2, 1, 3, 9);

    addEdge(3, 1, 4, 23);

    addEdge(4, 2, 5, 4);

    addEdge(5, 2, 6, 25);

    addEdge(6, 3, 7, 29);

    addEdge(7, 6, 8, 5);

    addEdge(8, 7, 9, 30);

    addEdge(9, 8, 10, 1);

    addEdge(10, 8, 11, 6);

  

    / * наше дерево укоренено в узле 0 на глубине 0 * /

    int root = 0, parent_of_root=-1, depth_of_root=0;

  

    / * DFS на дереве для настройки:

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

     * более глубокий конец каждого края * /

    dfs(root, parent_of_root, depth_of_root, n);

  

    int chain_heads[N];

  

    / * мы не инициализировали никаких цепных головок * /

    memset(chain_heads, -1, sizeof(chain_heads));

  

    / * Хранит количество ребер для построения сегмента

       дерево. Изначально мы не прошли ни одного края. * /

    int edge_counted = 0;

  

    / * мы начинаем с заполнения 0-й цепочки * /

    int curr_chain = 0;

  

    / * HLD дерева * /

    hld(root, n-1, &edge_counted, &curr_chain, n, chain_heads);

  

    / * ST обособленных краев * /

    construct_ST(0, edge_counted, 1);

  

    / * Поскольку индексы основаны на 0, узел 11 означает индекс 11-1,

       8 означает 8-1 и т. Д. *

    int u = 11, v  = 9;

    cout << "Max edge between " << u << " and " << v << " is ";

    maxEdge(u-1, v-1, n, chain_heads);

  

    // Изменить значение ребра с номером 8 (индекс 8-1) на 28

    change(8-1, 28, n);

  

    cout << "After Change: max edge between " << u << " and "

         << v << " is ";

    maxEdge(u-1, v-1, n, chain_heads);

  

    v = 4;

    cout << "Max edge between " << u << " and " << v << " is ";

    maxEdge(u-1, v-1, n, chain_heads);

  

    // Изменим значение ребра № 5 (индекс 5-1) на 22

    change(5-1, 22, n);

    cout << "After Change: max edge between " << u << " and "

         << v << " is ";

    maxEdge(u-1, v-1, n, chain_heads);

  

    return 0;

}

Выход:

Max edge between 11 and 9 is 30
After Change: max edge between 11 and 9 is 29
Max edge between 11 and 4 is 25
After Change: max edge between 11 and 4 is 23

Эта статья предоставлена Яшем Варяни . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Тяжелое Легкое Разложение | Набор 2 (реализация)

0.00 (0%) 0 votes