Тяжёлые пути
Также: Heavy-light decomposition · HLD · heavy path decomposition · разбиение на тяжёлые и лёгкие пути · тяжёлые и лёгкие рёбра · запросы на путях дерева · path queries
Как отвечать на вопросы о пути между двумя вершинами дерева — максимум, сумма, прибавить ко всем — за O(log² n). Из каждой вершины продолжаем путь в самое большое поддерево; такие тяжёлые пути режут любой путь в дереве на O(log n) кусков, а в правильной нумерации каждый кусок — отрезок массива.
Ниже рельеф гор над Алматы со спутникового радара NASA, клетки по 165 метров. Для каждой клетки посчитано, куда из неё стекает вода, и получилось дерево: у каждой клетки один «родитель» — клетка ниже по течению, а корни — края карты, где вода уходит из гор. Каждый цветной поток — тяжёлый путь: поднимаясь против течения, он на каждой развилке уходит в тот приток, из которого приходит больше всего воды. Пунктир — настоящие русла из OpenStreetMap. Алгоритм о реках ничего не знал, но тяжёлые пути легли в них сами. Коснитесь любой точки, чтобы увидеть, куда из неё стечёт вода.
От Большого Алматинского озера вода проходит 117 шагов до края гор, и весь этот путь — один тяжёлый путь: 115 из 118 его клеток лежат ближе 350 метров к руслу Большой Алматинки. От Медеу — 53 шага по одному тяжёлому пути, 52 клетки из 54 у русла Малой Алматинки. А от склона у Шымбулака — он выбран на карте — вода проходит три тяжёлых пути: ручей, поток побольше, Малая Алматинка. Профиль под картой показывает, почему переходов мало: в каждой оранжевой точке площадь бассейна, из которого собирается вода, по меньшей мере удваивается.
Ниже профиля — та же дорога в номерах. Клетки, все 28 341, выписаны в один ряд в особом порядке, и путь воды, сколько бы клеток в нём ни было, занимает в этом ряду несколько сплошных отрезков. Весь бассейн выше выбранной клетки — один отрезок, светлый. Это и нужно, чтобы задавать вопросы о путях в дереве через дерево отрезков.
Идея
У каждой вершины дерева выберем тяжёлого ребёнка — того, у кого в поддереве больше всего вершин. Ребро к нему назовём тяжёлым, к остальным детям — лёгкими. Тяжёлые рёбра складываются в тяжёлые пути: у каждой вершины не больше одного тяжёлого ребра вниз и не больше одного вверх, поэтому это цепочки, и каждая вершина лежит ровно на одной. Верхнюю вершину цепочки назовём её головой. В сети стока поддерево клетки — её бассейн, и тяжёлый ребёнок — тот приток, который приносит больше воды. Поэтому тяжёлые пути здесь — это главные русла.
Путь из любой вершины к корню переходит с одного тяжёлого пути на другой не больше log₂ n раз. Обойдите дерево в глубину, заходя сначала в тяжёлого ребёнка, и пронумеруйте вершины в порядке обхода: каждый тяжёлый путь станет отрезком номеров. Любой путь в дереве — несколько таких отрезков, а на отрезках работает дерево отрезков.
Чтобы ответить на вопрос о пути между вершинами a и b, поднимаемся из той, у которой голова цепочки глубже: весь кусок от головы до неё — отрезок номеров, его спрашиваем у дерева отрезков и переходим к родителю головы. Когда обе вершины оказались на одной цепочке, остаётся последний отрезок между ними. Так же устроены изменения: «прибавить x всем вершинам пути» — это прибавление на нескольких отрезках.
Почему кусков мало
На пути от любой вершины к корню дерева из n вершин не больше log₂ n лёгких рёбер.
Пусть ребро из u в её родителя p лёгкое. Тогда у p есть тяжёлый ребёнок h ≠ u, и в его поддереве не меньше вершин, чем в поддереве u. В поддерево p входят оба поддерева и сама p: size(p) ≥ 1 + 2 · size(u) > 2 · size(u). Значит, при каждом подъёме по лёгкому ребру размер поддерева больше чем удваивается. Начинается он с единицы и не превышает n, поэтому лёгких рёбер на пути не больше log₂ n.
В сети стока это читается без формул: когда ручей не продолжается сам, а вливается в другой поток, бассейн того потока не меньше бассейна ручья, и после слияния площадь по меньшей мере удваивается. Самый большой бассейн на этой карте, у Большой Алматинки, — 219 км², около восьми тысяч клеток, log₂ ≈ 13, а на деле больше пяти таких впадений не встречается нигде. Гидрологи знают похожую величину давно: порядок водотока по Хортону — Стралеру растёт на единицу, только когда сливаются два потока одного порядка, и потому тоже не больше логарифма числа истоков.
Если при обходе в глубину сначала заходить в тяжёлого ребёнка, то номера вершин каждого тяжёлого пути идут подряд, и номера вершин каждого поддерева идут подряд. Путь между любыми двумя вершинами состоит не больше чем из 2 log₂ n + 1 отрезков номеров, и подъём по головам находит их все.
Тяжёлый ребёнок получает номер сразу после родителя, потому что обход заходит в него первым, — отсюда первое утверждение. Второе верно для любого обхода в глубину: он не покидает поддерево, пока не обошёл его целиком.
Теперь подъём. Пусть головы цепочек a и b разные и голова цепочки a не выше головы цепочки b. Покажем, что общий предок a и b лежит выше головы цепочки a, то есть весь кусок от головы до a — часть пути. Если бы общий предок лежал в поддереве головы, он был бы предком a внутри этого поддерева, а такие вершины — ровно кусок цепочки a от головы до a. Тогда b тоже лежала бы в поддереве головы, а её цепочка, не проходя через голову цепочки a, начиналась бы глубже — вопреки выбору. Значит, кусок от головы до a берём целиком и переходим к родителю головы по лёгкому ребру. Каждый такой шаг тратит одно лёгкое ребро на пути от a или от b к корню, всего их не больше 2 log₂ n, и ещё один отрезок — последний, на общей цепочке.
На каждом отрезке дерево отрезков отвечает за O(log n), поэтому вопрос или изменение на пути стоит O(log² n). Вопрос о поддереве — один отрезок, O(log n). Нумерация для путей и для поддеревьев одна и та же, и одно дерево отрезков отвечает на оба вида вопросов.
Код
Сначала сеть стока. Рельеф «заливают» от краёв, всякий раз продолжая с самой низкой клетки, до которой вода уже дошла, — так в геоинформатике считают сток по рельефу (Ричард Барнс с соавторами назвали этот способ priority-flood). Клетка, до которой заливка дошла из соседа, стекает в этого соседа. Потом размеры поддеревьев, тяжёлые дети и нумерация — без рекурсии: у речных деревьев сотни уровней, у общих деревьев бывают и сотни тысяч. И напоследок ливни: дождь в клетке прибавляет воду всем клеткам ниже по течению, а вопрос — наибольший расход на пути по руслам между двумя клетками. Каждый ответ сверяется с подсчётом напрямую.
Тяжёлых путей 11 211, но почти все они — ручьи в одну-две клетки; самые длинные — 191, 150 и 145 клеток. Путь между двумя клетками одного бассейна режется в среднем на 4,4 отрезка номеров и ни разу больше чем на 10, а подсчёт напрямую проходит в среднем 59 клеток на вопрос. Разница растёт с глубиной дерева: на реке в тысячу клеток подсчёт напрямую пройдёт тысячу, а отрезков останется несколько.
Сколько это стоит
| Способ | Подготовка | Путь: вопрос или изменение | Поддерево |
|---|---|---|---|
| Напрямую, по родителям | O(n) | O(длина пути), до O(n) | O(размер поддерева) |
| Тяжёлые пути и дерево отрезков | O(n) | O(log² n) | O(log n) |
| Двоичный подъём | O(n log n) | O(log n), но только без изменений | — |
| Динамические деревья Слитора — Тарьяна | O(n) | O(log n) в среднем на операцию, и дерево можно перестраивать | — |
Замер на деревьях, похожих на реки: каждая новая клетка впадает в одну из восьми предыдущих, так что дерево глубокое — длинный поток с короткими притоками. Меряются только 300 действий, ливни и вопросы о максимуме на пути, без подготовки: подготовка у тяжёлых путей — O(n), один обход.
Подсчёт напрямую растёт как длина пути, то есть линейно: на 64 000 вершинах он медленнее тяжёлых путей в сорок раз на Python и больше чем в десять раз на Go. Тяжёлые пути почти не замечают роста: число отрезков растёт как логарифм.
Где легко ошибиться
- Тяжёлый — по размеру поддерева, а не по глубине. Если продолжать путь в самое глубокое поддерево, получится «длинный путь» — разбиение, где переходов бывает порядка √n. Оценка log₂ n держится только на удвоении размера.
- Подниматься из той вершины, чья голова глубже, а не из той, что сама глубже. Вершина может быть глубокой, но лежать на длинной цепочке с головой у самого корня; подъём из неё перепрыгнет общего предка.
- Значения на рёбрах. Если вопрос о рёбрах — например, о самом узком участке реки между точками, — значение ребра хранят в нижней его вершине, а на последнем отрезке общего предка исключают: его вершина хранит ребро, которое в путь не входит.
- Рекурсия. Рекурсивный обход упадёт на дереве-цепочке из ста тысяч вершин; обход со стеком, как в коде, — нет.
- Прибавление и максимум вместе. Дереву отрезков нужна отложенная операция: прибавка, которая висит на узле и не проталкивается вниз, пока не понадобится. Без неё прибавление на отрезке стоит его длину.
Где работает
В олимпиадах тяжёлые пути — стандартный ответ на вопросы о путях дерева с изменениями: прибавить на пути, найти максимум или сумму, перекрасить. Без изменений обычно хватает наибольшего общего предка и префиксных сумм от корня. Если дерево само меняется — рёбра удаляют и добавляют, — нужны динамические деревья Слитора и Тарьяна; их оценка держится на той же границе лёгких рёбер. Тяжёлые пути дают и наибольшего общего предка без таблиц: подъём по головам до общей цепочки — это O(log n) шагов, а на общей цепочке ответ — та из двух вершин, что выше. В сетях стока по рельефу то же разбиение выделяет главные русла: по ним вода приходит к выходу из бассейна.
История
Разбиение на тяжёлые и лёгкие рёбра появилось в 1981 году в работе Дэниела Слитора и Роберта Тарьяна о динамических деревьях — структуре, где лес можно разрезать и сращивать и при этом спрашивать о путях за логарифм. Граница «не больше log n лёгких рёбер на пути к корню» была в ней главным инструментом оценки. В олимпиадное программирование приём пришёл позже, вместе с деревом отрезков, и стал известен под английским сокращением HLD.
Задачи
Ливни над настоящими горами: дождь в клетке добавляет воду всем клеткам ниже по течению, а вопрос — наибольший расход на пути по руслам между двумя клетками. Среди тестов — та же сеть стока гор над Алматы и река-цепочка в сто тысяч клеток, на которой подсчёт напрямую не успевает.
ПаводокДанные: Рельеф гор над Алматы: NASA SRTM v3 (1″) через Open Topo Data, общественное достояние Реки гор над Алматы © участники OpenStreetMap, ODbL (выгрузка 24.10.2026)