Доброго времени суток всем.

Сегодня я хочу рассказать немного о написании элегантной структуру данных — Heavy-light decomposition (далее просто HLD).

Многие из вас, наверное, сталкивались с задачами вида "дано взвешенное дерево, запросы модификации ребер и запросы нахождения минимума на ребрах между двумя вершинами". HLD умеет довольно просто решать эту и многие другие задачи.

Для начала краткое описание структуры.

// Более полное описание есть на e-maxx.

Heavy-light decomposition — это такая разбивка графа на непересекающиеся по вершинам или ребрам пути, что на пути от любой вершины до корня этого дерева мы сменим не более log(N) путей. Если мы научимся строить такие пути, то с помощью дополнительных структур (дерево отрезков (или просто ДО), например) сможем быстро отвечать на запросы.

Назовем ребро тяжелым, если поддерево сына, в которого ведет это ребро, будет по размеру не менее половины поддерева отца. Другими словами, . Заметим, что с вершины вниз может выходить не более одного тяжелого ребра.

"И что это нам дает?" — спросите Вы. А дает это нам следующее: если мы возьмем все вершины, из которых не выходит тяжелое ребро, и будем подниматься к корню, пока его не достигнем или не пройдем по легкому ребру, то это и будут нужные нам пути.

Построив дерево отрезков над каждым из путей, мы сможем за log²(N) отвечать на самые разные запросы между двумя вершинами (максимум и т.д.). Нужно будет аккуратно подниматься от вершин к их lca (наименьший общий предок) и производить запросы на ДО или на еще чём-то.

Теперь о количестве кода..

Первый раз, когда я попробовал написать эту структуру для задачи, то код был, мягко говоря, немаленький. Я честно искал lca, честно строил над каждым из путей ДО и еще много чего. Я код еще и дебажил немало. И сейчас стоит поговорить о том, как уменьшить его количество.

О построении HLD

Первое, что хочется исправить, так это немного неудобное построение. Хоть и написать его не составить большинству труда, но мне и сейчас в таком виде, как описано выше, его писать не очень удобно. Вот бы взять, и за один-два простеньких dfs-a это все построить...

И это возможно. Можно строить декомпозицию так: пускай мы находимся в некоторой вершине. Она принадлежит некоторому пути. Рассмотрим всех сынов этой вершины — мы можем продолжить этот путь только в одного, а все остальные сыны станут началом новых путей. В какого же сына надо продолжить этот путь? Правильно, в того, у которого наибольшее поддерево. Значит, один dfs нужен, чтобы подсчитать размеры поддеревьев, а другой для непосредственного построения декомпозиции.

Об отдельных структурах для каждого пути

Далее я буду рассказывать на примере ДО, так как часто именно оно нужно для задач.
Следующая мысль после того, как мы научились просто строить HLD, у меня была приблизительно такая: "Блин, это же надо еще и для каждого пути ДО писать". Да, это не так сложно, но немного было для меня неудобно. Но потом можно понять, что достаточно одного ДО. Необходимо так перенумеровать вершины, чтобы для каждого пути все вершины были на одном подотрезке. Имеем, что нужно только одно ДО.

О честном нахождении lca

Еще одна вещь, через которую разрастался код, — отдельное написание поиска lca. Как же с этим можно бороться?

Оказывается, что не нужно искать lca я явном виде. Давайте поступим по следующему алгоритму: рассмотрим два пути, на которых сейчас наши вершины. Если они на одном пути, то это просто запрос на ДО. А если нет? Тогда давайте выберем путь, у которого наивысшая вершина ниже. Далее просто перейдем в предка этой вершины. Будем так продолжать, пока не придем в один путь. Параллельно всем этим подъемам будем делать запросы на ДО, тем самым ища ответ.

Имеем, что ответ на запрос и нахождение lca можно делать одновременно.

Материалы

Я очень благодарен сайту e-maxx, на котором есть хорошее описание (клац) этой структуры. Я много в чем опирался именно на эту статью.

Еще хорошие материалы есть здесь.

И короткая реализация есть здесь

Бонус

Можно проверить свою HLD на этой задаче. А здесь мой код к ней.

Другие задачи: QTREE, Aladdin and the Return Journey.

P.S. Я понимаю, что простота этой структуры — штука относительная. Я старался объяснить, как мне писать проще. Буду очень рад, если статья кому-то пригодится.

P.P.S Это моя первая статья. Буду рад услышать конструктивную критику, замечания по поводу статьи.