Тяжело-лёгкая декомпозиция: путь в дереве как логарифм отрезков

Если ты знаешь, почему путь в дереве пересекает не больше log n лёгких рёбер и как выложить цепочки в массив под дерево отрезков, листай до «Теперь сам».

Как думаешь, как сложить значения на пути быстро

Сеть трубопроводов без колец - дерево. В каждом узле датчик с текущим давлением, показания меняются. Диспетчер спрашивает: какова сумма давлений на пути от узла u до узла v? Подниматься от обоих концов к общему предку и складывать - это O(глубины), и на дереве глубиной в 763 узла на запрос уходят сотни шагов.

Для массива мы умеем такое за логарифм. Прежде чем читать дальше, ответь себе: можно ли выложить вершины дерева в массив так, чтобы любой путь распадался на НЕМНОГО отрезков этого массива? Один отрезок на путь - невозможно (путь ветвится в предке). Сколько тогда?

На что это похоже

Метро и маршрутки. Город - дерево улиц. По главным улицам проложены линии метро: по линии едешь быстро, сколько угодно станций за одну поездку. Маршрутки ходят по второстепенным улицам и везут только до ближайшей станции. Если линии проложены по самым «населённым» направлениям, любая поездка по городу - несколько пересадок, а не сотня остановок. Тяжёлые цепочки - линии метро, лёгкие рёбра - пересадки, и пересадок на любом маршруте мало.

Механизм: тяжёлые сыновья, цепочки, позиции

1. размеры поддеревьев; у каждой вершины тяжёлый сын - с наибольшим
   поддеревом. Ребро к нему тяжёлое, к остальным сыновьям - лёгкие
2. тяжёлые рёбра образуют цепочки. Выкладываем вершины в массив так,
   чтобы каждая цепочка шла подряд сверху вниз; голова(v) - верх
   цепочки, в которой лежит v
3. на массиве - дерево Фенвика или дерево отрезков
4. запрос по пути u–v:
   пока голова(u) ≠ голова(v):
       взять ту из двух, у кого голова глубже, - пусть u
       учесть отрезок [позиция(голова(u)), позиция(u)]
       u = отец(голова(u))              ← прыжок через лёгкое ребро
   теперь u и v на одной цепочке: учесть отрезок между ними

Почему цепочек мало. Если ребро от v к сыну c лёгкое, то у v есть сын не меньше c (тяжёлый), значит размер(v) ≥ 2 · размер(c). Каждый подъём по лёгкому ребру как минимум удваивает размер поддерева, а больше n он не бывает - лёгких рёбер на пути к корню не больше log₂ n. Путь u–v - это два подъёма к общему предку: не больше 2·log₂ n цепочек, на каждой - запрос к отрезку за O(log n). Итого O(log² n) на запрос, изменение значения - одна точка массива, O(log n).

Правило

Тяжело-лёгкая декомпозиция объявляет тяжёлым ребро к сыну с наибольшим поддеревом, выкладывает тяжёлые цепочки в массив подряд и строит над массивом дерево Фенвика или отрезков. Подъём по лёгкому ребру удваивает поддерево, поэтому любой путь пересекает не больше 2·log₂ n цепочек; запрос по пути - столько же запросов к отрезкам, O(log² n), изменение вершины - O(log n).

Разбор: путь из восьми вершин

           1 (8)                   в скобках - размер поддерева
          /     \
       2 (5)     3 (2)             тяжёлые рёбра: 1–2, 2–4, 4–6, 3–8
       /   \        \
    4 (3)  5 (1)    8 (1)          цепочки:  [1 2 4 6]  [7]  [5]  [3 8]
    /   \
  6 (1) 7 (1)                      массив:   1 2 4 6 | 7 | 5 | 3 8

путь 7 – 8:
  голова(7) = 7 (глубина 3), голова(8) = 3 (глубина 1)
  глубже 7 → отрезок [7], прыжок к отцу: u = 4
  голова(4) = 1 (глубина 0), голова(8) = 3 (глубина 1)
  глубже 3 → отрезок [3 8], прыжок: v = отец(3) = 1
  обе на цепочке [1 2 4 6]: отрезок от 1 до 4 → [1 2 4]
  путь 7–4–2–1–3–8 = три отрезка массива

Подъём от 7 к 4 - это лёгкое ребро: поддерево выросло с 1 до 3. От 3 к 1 - тоже лёгкое, с 2 до 8. На каждом прыжке размер хотя бы удваивается.

Разбор: двадцать тысяч вершин, глубина 763

Программа строит глубокое дерево, раскладывает его на цепочки, держит значения в дереве Фенвика и выполняет 2000 случайных операций - изменения значений и суммы по пути, - сверяя каждую сумму с наивным подъёмом по отцам.

import math
import random

rng = random.Random(12)
n = 20000
otec = [-1] + [rng.randrange(max(0, v - 50), v) for v in range(1, n)]
deti = [[] for _ in range(n)]
for v in range(1, n):
    deti[otec[v]].append(v)
poryadok = [0]
for v in poryadok:
    poryadok.extend(deti[v])
glub = [0] * n
for v in poryadok[1:]:
    glub[v] = glub[otec[v]] + 1

razmer = [1] * n                      # 1. размеры и тяжёлый сын
for v in reversed(poryadok[1:]):
    razmer[otec[v]] += razmer[v]
tyazh = [max(deti[v], key=lambda u: razmer[u]) if deti[v] else -1
         for v in range(n)]

golova, pos = [0] * n, [0] * n        # 2. цепочки подряд в массиве
stek, k = [0], 0
while stek:
    v = stek.pop()
    while v != -1:                    # идём по тяжёлой цепочке вниз
        pos[v], k = k, k + 1
        for u in deti[v]:
            if u != tyazh[v]:
                golova[u] = u         # лёгкий сын начнёт свою цепочку
                stek.append(u)
        if tyazh[v] != -1:
            golova[tyazh[v]] = golova[v]
        v = tyazh[v]

fen = [0] * (n + 1)                   # 3. дерево Фенвика по позициям


def dobavit(i, d):
    i += 1
    while i <= n:
        fen[i] += d
        i += i & -i


def prefiks(i):                       # сумма позиций 0..i−1
    s = 0
    while i > 0:
        s += fen[i]
        i -= i & -i
    return s


znach = [rng.randrange(100) for _ in range(n)]
for v in range(n):
    dobavit(pos[v], znach[v])


def summa_puti(u, v):                 # 4. запрос: прыгаем по цепочкам
    s, cepochek = 0, 0
    while golova[u] != golova[v]:
        if glub[golova[u]] < glub[golova[v]]:
            u, v = v, u
        h = golova[u]
        s += prefiks(pos[u] + 1) - prefiks(pos[h])
        u, cepochek = otec[h], cepochek + 1
    if pos[u] > pos[v]:
        u, v = v, u
    s += prefiks(pos[v] + 1) - prefiks(pos[u])
    return s, cepochek + 1


def naivno(u, v):                     # поднимаемся по отцам
    s, shagi = 0, 0
    while u != v:
        if glub[u] < glub[v]:
            u, v = v, u
        s, u, shagi = s + znach[u], otec[u], shagi + 1
    return s + znach[u], shagi


maks_cep = shagi_vsego = zaprosov = 0
for _ in range(2000):
    if rng.random() < 0.5:            # изменение значения
        v, novoe = rng.randrange(n), rng.randrange(100)
        dobavit(pos[v], novoe - znach[v])
        znach[v] = novoe
    else:
        u, v = rng.randrange(n), rng.randrange(n)
        (s, c), (s2, sh) = summa_puti(u, v), naivno(u, v)
        assert s == s2
        maks_cep, shagi_vsego = max(maks_cep, c), shagi_vsego + sh
        zaprosov += 1
print("глубина дерева:", max(glub), " log2 n =", round(math.log2(n), 1))
print("цепочек на путь, не больше:", maks_cep)
print("наивный подъём, вершин на путь в среднем:",
      round(shagi_vsego / zaprosov))

глубина дерева: 763  log2 n = 14.3
цепочек на путь, не больше: 9
наивный подъём, вершин на путь в среднем: 292

Все суммы совпали с наивным подъёмом. Путь длиной в сотни вершин ни разу не распался больше чем на 9 цепочек - меньше даже log₂ n, хотя гарантия вдвое слабее. Каждая цепочка - два вызова prefiks по log n шагов: несколько сотен действий на запрос вместо обхода трёхсот вершин, и разрыв растёт с глубиной дерева.

Что ломается без этого

Первая ошибка - выбрать тяжёлым сына не по размеру поддерева, а по глубине или первым по списку: гарантия удвоения пропадает, и на специально построенном дереве путь режется на Θ(√n) или даже Θ(n) кусков. Вторая - выкладывать вершины в массив обычным обходом, не идя первым делом по тяжёлому сыну: цепочка перестаёт лежать подряд, и «отрезок цепочки» оказывается не отрезком массива. Третья - в конце запроса забыть общую цепочку или учесть общего предка дважды. Четвёртая - на дереве глубиной в сотни тысяч писать обход рекурсией - стек Python кончится раньше; в программе всё построено циклами.

Зачем это в работе

Запросы по пути в дереве с изменениями: сумма или максимум нагрузки на пути в сети без колец, самое узкое место на маршруте в иерархии каналов, «добавить значение всем узлам на пути» в задачах учёта. Тот же приём «перевести дерево в массив, где нужные куски лежат подряд» уже встречался в этом разделе: обход с временами входа и выхода делает поддерево отрезком. Тяжело-лёгкая декомпозиция делает то же для путей - и вместе они закрывают почти любой запрос к дереву через структуры для массивов.

Теперь сам

Дерево-«метла»: цепочка 1 – 2 – … – 1000, и к вершине 1 дополнительно подвешены листья 1001…1999 по одному. Какие рёбра тяжёлые? На сколько цепочек распадётся путь от 1000 до 1500?