Слияние меньшего в большее: ответы по всем поддеревьям за n · log n

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

Как думаешь, сколько стоит собрать наборы всех поддеревьев

Дерево папок на диске, в каждом файле - тег. Для каждой папки нужно число разных тегов во всём её содержимом. Решение очевидное: обойти дерево снизу вверх, набор тегов папки - объединение наборов вложенных папок плюс свои файлы.

Прежде чем читать дальше, ответь себе: сколько раз будет скопирован тег файла, лежащего на глубине тысяча, если каждая папка собирает НОВОЕ множество из множеств детей? И что изменится, если папка не собирает новое, а берёт множество одного из детей и дописывает в него остальное?

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

Объединение двух компаний. Когда маленький стартап покупает гигант, все сотрудники гиганта не переезжают в офис стартапа - переезжают люди стартапа к гиганту. Правило «меньшие переезжают к большим» гарантирует, что каждый человек переезжает редко: после каждого переезда его компания хотя бы вдвое больше прежней, а удваиваться до размера всей отрасли можно лишь несколько раз.

То же правило уже встречалось в непересекающихся множествах: объединение по рангу подвешивает меньшее дерево к большему - и по той же причине высота остаётся логарифмической.

Механизм: забрать большой набор, влить маленькие

обходим вершины так, чтобы дети шли раньше отца
для вершины v:
    набор = {свой элемент}
    для каждого ребёнка u:
        m = набор(u)
        если |m| > |набор|:  поменять набор и m   ← ключевая строка
        влить m в набор                 (|m| операций)
    ответ(v) = |набор|

Счёт переносов. Посмотрим на один элемент x. Его переносят, только когда он лежит в МЕНЬШЕМ из двух сливаемых наборов. После слияния набор, где лежит x, не меньше суммы двух, то есть хотя бы вдвое больше прежнего. Набор не может быть больше n, удваиваться от 1 до n можно log₂ n раз. Элементов n, переносов всего ≤ n · log₂ n. Без «ключевой строки» гарантии нет: на цепочке набор каждого уровня копируется на уровень выше целиком.

Важная деталь: набор, который «забрали», нельзя потом использовать как набор ребёнка - его уже изменили. Ответ для ребёнка надо записать ДО того, как его набор отдан отцу.

Правило

Когда ответ вершины собирается из наборов её детей, самый большой набор ребёнка забирают целиком, а меньшие вливают в него поэлементно. Элемент переносится только из меньшего набора в больший, и его набор после этого хотя бы удваивается - не больше log₂ n переносов на элемент, O(n · log n) операций с множеством на всё дерево. Ответ ребёнка фиксируют до того, как его набор забрал отец.

Разбор: цепочка из пяти вершин

цепочка 1 – 2 – 3 – 4 – 5, корень 1, цвета: 1:к 2:с 3:к 4:з 5:с

СОБИРАЕМ НОВЫЙ НАБОР НА КАЖДОМ УРОВНЕ
5: {с}                       переносов 0
4: {з} ∪ {с}                 1      (влили набор 5)
3: {к} ∪ {з с}               2
2: {с} ∪ {к з с}             3
1: {к} ∪ {к з с}             3      всего 9 ≈ n²/2

МЕНЬШЕЕ В БОЛЬШЕЕ
5: {с}
4: размеры равны → вливаем {с} в {з}                         1
3: забираем {з с}, вливаем {к}                               1
2: забираем {к з с}, вливаем {с} (уже был)                   1
1: забираем {к з с}, вливаем {к}                             1   всего 4

На цепочке длины n разница - n²/2 против n: каждый уровень вливает только свой элемент.

Разбор: пятьдесят тысяч вершин

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

import math
import random

rng = random.Random(9)
n = 50000
otec = [-1] + [rng.randrange(max(0, v - 3), v) for v in range(1, n)]
cvet = [rng.randrange(1000) for _ in range(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])


def razlichnye(umno):                 # число разных цветов в поддереве
    mnozh = [None] * n
    otvet = [0] * n
    perenosy = 0
    for v in reversed(poryadok):      # дети раньше отца
        nabor = {cvet[v]}
        for u in deti[v]:
            m = mnozh[u]
            if umno and len(m) > len(nabor):
                nabor, m = m, nabor   # вливаем меньшее в большее
            perenosy += len(m)
            nabor |= m
            mnozh[u] = None
        mnozh[v] = nabor
        otvet[v] = len(nabor)
    return otvet, perenosy


o1, p1 = razlichnye(umno=False)
o2, p2 = razlichnye(umno=True)
assert o1 == o2
print("вливание в отцовский набор:", p1, "переносов")
print("меньшее в большее:         ", p2, "переносов")
print("n · log2 n =", round(n * math.log2(n)))

вливание в отцовский набор: 24619992 переносов
меньшее в большее:          70485 переносов
n · log2 n = 780482

Ответы совпали, а работы в 350 раз меньше. Даже оценка n · log₂ n здесь с запасом в десять раз: разных цветов всего тысяча, и наборы не растут выше тысячи. Наивный вариант копирует наборы до тысячи элементов на каждом из десятков тысяч уровней.

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

Первая ошибка - сравнивать размеры, но вливать всё равно в «свой» набор вершины: выигрыш появляется только тогда, когда большой набор ЗАБИРАЮТ, а не копируют. nabor = nabor | m создаёт новое множество и копирует оба - это снова квадрат; нужно nabor |= m по большому набору. Вторая - забыть, что забранный набор принадлежал ребёнку: если ответ ребёнка считать потом по его набору, он окажется испорчен отцовскими элементами. Третья - применять приём к величинам, которые не «вливаются» поэлементно: медиана поддерева так не считается без дополнительной структуры.

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

Агрегаты по иерархиям: уникальные теги в папке со всем содержимым, число разных клиентов в регионе со всеми филиалами, самый частый тип события в поддереве вызовов профилировщика. Тот же принцип «меньшее к большему» стоит в объединении по рангу у непересекающихся множеств, в слиянии куч и в переразмеривании хеш-таблиц при объединении словарей: a.update(b) дешевле, когда b меньше. Если объединяешь коллекции многократно, порядок аргументов - это разница между n log n и n².

Теперь сам

Корень с тремя детьми, у детей наборы размеров 100, 5 и 40, у корня свой элемент. Сколько переносов сделает «меньшее в большее» при обработке корня и сколько - наивный вариант, вливающий всё в набор корня?