18.4 Офлайн-алгоритмы¶

Этот раздел посвящён офлайн-обработке запросов на дереве. Ранее мы обсуждали онлайн-алгоритмы: они отвечают на запросы по одному, в том порядке, в котором запросы приходят. Но во многих задачах это вовсе не обязательно. Если нам заранее известны все запросы, то часто можно обработать их выгоднее — проще по коду, а иногда и быстрее по асимптотике.

В этом и состоит идея офлайн-подхода:

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

В этом разделе мы разберём два классических приёма:

слияние структур данных по поддеревьям;
офлайн-нахождение LCA с помощью DSU (union-find).

Когда офлайн-подход полезен¶

Офлайн-алгоритмы особенно удобны, когда:

все запросы известны заранее;
ответы не нужно печатать немедленно после чтения запроса;
можно сначала выполнить один общий DFS по дереву;
запросы естественно группируются по вершинам.

Например, если нужно для многих вершин узнать что-то о их поддереве, удобно обойти дерево снизу вверх и в каждой вершине собрать агрегированную информацию по её детям.

Идея 1. Слияние структур данных по поддеревьям¶

Постановка задачи¶

Пусть дано корневое дерево. В каждой вершине хранится некоторое значение. Нужно ответить на запросы вида:

«Сколько вершин со значением x находится в поддереве вершины s?»

Например, если в поддереве вершины 4 встречаются значения

3,
4,
3,
1,

то ответ на запрос (s = 4, x = 3) равен 2.

Наивная идея¶

Для каждой вершины можно было бы отдельно пройти по всему её поддереву и посчитать частоты значений. Но это слишком медленно: если делать так для многих вершин, получится вплоть до O(n^2).

Нужна идея лучше: вычислять структуру для вершины через уже готовые структуры её детей.

Структура данных в вершине¶

Для каждой вершины v будем хранить словарь:

ключ — значение в вершине;
значение — сколько раз оно встречается в поддереве v.

То есть cnt[v][x] — число вершин со значением x в поддереве v.

Тогда после построения cnt[v] любой запрос для вершины v решается сразу:

ответ = cnt[v][x], если ключ есть;
иначе ответ = 0.

Как строить `cnt[v]`¶

Очень естественный DFS снизу вверх:

создаём словарь для самой вершины v;
добавляем в него её собственное значение;
рекурсивно обрабатываем всех детей;
сливаем словари детей в словарь v.

То есть:

cnt[v] = { value[v] : 1 } + все cnt[child]

Но здесь возникает важный вопрос: как сливать быстро?

Почему простое слияние может быть медленным¶

Представим, что мы всегда просто копируем все элементы из словаря ребёнка в словарь родителя. Тогда один и тот же элемент может переноситься слишком много раз.

Например, если дерево похоже на цепочку, а словари растут постепенно, суммарная стоимость может стать квадратичной.

Нужен стандартный трюк:

Приём small-to-large¶

При слиянии двух структур данных:

всегда добавляем меньшую структуру в большую;
если текущая структура родителя меньше, чем структура ребёнка, меняем их местами.

Тогда каждый элемент будет переходить только из меньшей структуры в большую. А раз после такого перехода размер структуры как минимум удваивается, то один элемент может быть перенесён не более чем O(log n) раз.

Это и даёт хорошую суммарную оценку.

Интуиция оценки `O(n log n)`¶

Пусть некоторый ключ-значение переехал из одного словаря в другой.

Это могло случиться только тогда, когда его словарь был меньшим. После слияния размер новой структуры как минимум вдвое больше старой. Значит:

сначала элемент был в структуре размера 1,
потом мог оказаться в структуре размера хотя бы 2,
потом хотя бы 4,
потом хотя бы 8,
и так далее.

Больше чем log n таких удвоений не бывает.

Следовательно, каждый элемент участвует в дорогостоящем переносе лишь O(log n) раз, а вся обработка получается эффективной.

Пример¶

Рассмотрим вершину 4 и её детей 7, 8 и 9.

Пусть значения такие:

value[4] = 3
value[7] = 4
value[8] = 3
value[9] = 1

Тогда:

для вершины 7 словарь: {4: 1}
для вершины 8 словарь: {3: 1}
для вершины 9 словарь: {1: 1}
старт для вершины 4: {3: 1}

После слияния получим:

{3: 2, 4: 1, 1: 1}

Значит:

число троек в поддереве 4 равно 2;
число единиц равно 1;
число четвёрок равно 1.

C++: small-to-large для подсчёта значений в поддереве¶

Здесь:

g[v] — список детей/соседей;
val[v] — значение в вершине;
queries[v] — список запросов, относящихся к вершине v;
каждый запрос — это пара (x, id);
ответ на запрос пишется в ans[id].

  #include <bits/stdc++.h>
  using namespace std;

  struct Query {
  int x;
  int id;
  };

  int n, q;
  vector<vector<int>> g;
  vector<int> val;
  vector<vector<Query>> queries;
  vector<int> ans;

  vector<map<int,int>*> cnt;

  void dfs(int v, int p) {
  cnt[v] = new map<int,int>();
  (*cnt[v])[val[v]] = 1;

    for (int to : g[v]) {
        if (to == p) continue;
        dfs(to, v);

        if (cnt[v]->size() < cnt[to]->size()) {
            swap(cnt[v], cnt[to]);
        }

        for (auto it : *cnt[to]) {
            (*cnt[v])[it.first] += it.second;
        }
    }

    for (auto qu : queries[v]) {
        ans[qu.id] = (*cnt[v]).count(qu.x) ? (*cnt[v])[qu.x] : 0;
    }
  }

Что здесь важно¶

Мы храним указатель на map, чтобы можно было быстро менять местами структуры.
В строке

if (cnt[v]->size() < cnt[to]->size()) swap(cnt[v], cnt[to]);

реализован приём small-to-large.

После завершения dfs(v, p) структура cnt[v] уже содержит полную информацию по поддереву вершины v.

Замечания по структурам данных¶

Вместо map<int,int> можно использовать:

unordered_map<int,int> — часто быстрее на практике;
map<int,int> — стабильнее по времени и удобнее, если нужен упорядоченный обход;
массив частот — если значения маленькие и ограниченные.

Если значения вершин велики, но все известны заранее, можно сделать координатное сжатие.

Где ещё применяется small-to-large¶

Этот приём полезен не только для подсчёта частот. Его можно использовать, когда в поддереве нужно поддерживать:

множество различных значений;
сумму по различным ключам;
максимум частоты;
количество цветов/меток;
статистики по строкам или хешам.

Главная идея одна и та же: у вершины есть структура, которую мы получаем слиянием структур детей.

Идея 2. Офлайн-нахождение LCA¶

Теперь разберём вторую важную идею раздела — офлайн-нахождение наименьшего общего предка.

Напоминание: что такое LCA¶

LCA(u, v) — это самая глубокая вершина, являющаяся предком и для u, и для v.

Например, если вершины 5 и 8 лежат в разных ветках под вершиной 2, то их LCA равен 2.

Обычно LCA находят онлайн-методами:

бинарным подъёмом;
Euler tour + RMQ.

Но если все запросы известны заранее, существует очень красивый офлайн-алгоритм Тарьяна на основе DSU / union-find.

Общая идея алгоритма Тарьяна для LCA¶

Мы делаем DFS по дереву и одновременно поддерживаем систему непересекающихся множеств.

Что хранит DSU¶

На каждом шаге некоторые уже посещённые вершины объединяются в множества. Для каждого множества мы помним специальную вершину — представителя-ответа, то есть вершину, которая сейчас является самой высокой важной точкой для этого множества.

Обычно это хранится в массиве ancestor[find_set(v)].

Ключевая мысль¶

Когда DFS находится в вершине u, и мы видим запрос (u, v):

если вершина v уже была полностью или частично обработана,
то ответ на запрос равен ancestor[find_set(v)].

Почему? Потому что к этому моменту DSU уже «склеил» нужные поддеревья так, что представитель множества вершины v указывает как раз на LCA.

Это выглядит магически, но после пошагового разбора становится понятнее.

Пошаговая схема алгоритма¶

Для каждой вершины u делаем:

создаём для неё отдельное множество в DSU;
записываем ancestor[find_set(u)] = u;
запускаем DFS по каждому ребёнку to;
после возврата из ребёнка объединяем множества u и to;
после объединения снова ставим ancestor[find_set(u)] = u;
помечаем вершину u как посещённую;
просматриваем все запросы (u, v);
если v уже посещена, то ответ: LCA(u, v) = ancestor[find_set(v)].

Почему это работает¶

Когда DFS ещё не закончил обработку нужной общей вершины-предка, множества не успевают объединиться до нужного состояния. Но как только мы поднимаемся обратно по рекурсии, объединения происходят именно в том порядке, который соответствует дереву предков.

В момент, когда обе вершины запроса уже затронуты DFS, а мы находимся достаточно высоко, DSU уже хранит информацию о том, в каком объединённом поддереве лежит вторая вершина. Представитель ancestor этого множества и будет наименьшим общим предком.

Проще всего это воспринимать так:

DFS отвечает за правильный порядок обхода;
DSU отвечает за склейку уже обработанных частей дерева;
массив ancestor говорит, какая вершина является «верхней актуальной точкой» для текущего объединённого множества.

Небольшой пример¶

Пусть нужно ответить на два запроса:

LCA(5, 8)
LCA(2, 7)

Во время DFS может произойти следующее:

к моменту посещения вершины 8 вершина 5 уже была посещена;
DSU показывает, что вершина 5 сейчас находится в множестве, чья актуальная верхняя вершина — 2;
значит, LCA(5, 8) = 2.

Позже, когда обрабатывается вершина 7:

вершина 2 уже была посещена;
множество вершины 2 уже поднялось до вершины 1;
значит, LCA(2, 7) = 1.

C++: офлайн LCA по Тарьяну¶

#include <bits/stdc++.h>
using namespace std;

struct Query {
    int to;
    int id;
};

int n, q;
vector<vector<int>> g;
vector<vector<Query>> queries;
vector<int> ans;

vector<int> parent_dsu, rnk_dsu, ancestor;
vector<bool> used;

void make_set(int v) {
    parent_dsu[v] = v;
    rnk_dsu[v] = 0;
}

int find_set(int v) {
    if (v == parent_dsu[v]) return v;
    return parent_dsu[v] = find_set(parent_dsu[v]);
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (rnk_dsu[a] < rnk_dsu[b]) swap(a, b);
        parent_dsu[b] = a;
        if (rnk_dsu[a] == rnk_dsu[b]) rnk_dsu[a]++;
    }
}

void dfs(int v, int p) {
    make_set(v);
    ancestor[find_set(v)] = v;

    for (int to : g[v]) {
        if (to == p) continue;
        dfs(to, v);
        union_sets(v, to);
        ancestor[find_set(v)] = v;
    }

    used[v] = true;

    for (auto qu : queries[v]) {
        int u = qu.to;
        if (used[u]) {
            ans[qu.id] = ancestor[find_set(u)];
        }
    }
}

Как хранить запросы¶

Если есть запрос LCA(u, v), его удобно добавить в оба списка:

в queries[u] добавить (v, id);
в queries[v] добавить (u, id).

Тогда когда DFS придёт в одну из вершин, он сможет проверить, была ли уже посещена вторая.

Сложность¶

Если использовать DSU с:

сжатием пути;
объединением по рангу или размеру,

то алгоритм работает почти за линейное время:

O((n + q) * α(n)),

где α(n) — очень медленно растущая обратная функция Аккермана. На практике её можно считать константой.

То есть алгоритм фактически работает почти как O(n + q).

Сравнение с онлайн-методами¶

Бинарный подъём¶

Подходит, когда:

запросы приходят онлайн;
нужно быстро отвечать по одному;
дерево фиксировано.

Сложность:

подготовка O(n log n);
один запрос O(log n).

Euler tour + RMQ¶

Подходит, когда:

запросов очень много;
после хорошей подготовки хочется отвечать очень быстро.

Тарьян офлайн¶

Подходит, когда:

все запросы известны заранее;
хочется простой и красивый пакетный алгоритм;
удобнее обработать все запросы за один DFS.

Когда какой подход выбирать¶

Выбирайте small-to-large, если¶

запросы относятся к поддеревьям;
в каждой вершине нужно собрать статистику по её поддереву;
структура в вершине получается слиянием структур детей.

Выбирайте офлайн LCA Тарьяна, если¶

нужно ответить на много запросов LCA;
все запросы известны заранее;
не хочется строить таблицу бинарных подъёмов.

Важная методическая мысль¶

Оба алгоритма из этого раздела объединяет одна идея:

мы не отвечаем на запросы сразу, а встраиваем их обработку в DFS по дереву.

Это очень мощный взгляд на задачи по деревьям. Часто полезно спросить себя:

можно ли сгруппировать запросы по вершинам;
можно ли во время DFS накопить нужную информацию;
можно ли обрабатывать ответы не в порядке входа, а в том порядке, который удобен обходу.

Если ответ «да», то задача часто допускает красивое офлайн-решение.

Краткое резюме¶

1. Слияние структур данных¶

в каждой вершине строим структуру по её поддереву;
структуру родителя получаем слиянием структур детей;
используем приём small-to-large;
типичная сложность — O(n log n) или близкая к ней.

2. Офлайн LCA Тарьяна¶

все запросы известны заранее;
делаем DFS;
поддерживаем DSU множества обработанных вершин;
ответ на запрос получаем через ancestor[find_set(v)];
сложность почти линейная.

Что полезно потренировать¶

После этого раздела полезно уметь решать такие типы задач:

число различных цветов в поддереве вершины;
сколько раз значение x встречается в поддереве;
сумма частот по поддереву;
множество запросов LCA в офлайн-режиме;
расстояния между вершинами через LCA.

Напоминание: если известен l = LCA(u, v), то расстояние между вершинами вычисляется так:

dist(u, v) = depth[u] + depth[v] - 2 * depth[l]

Дополнительное упражнение¶

Попробуйте самостоятельно модифицировать small-to-large так, чтобы для каждой вершины находить:

какое значение встречается в её поддереве чаще всего;
сколько различных значений встречается хотя бы два раза.

Это хорошая тренировка на объединение словарей и аккуратную поддержку агрегатов.

Итог¶

Офлайн-алгоритмы на деревьях — это важный класс методов, который стоит знать отдельно от онлайн-решений. Они часто:

короче в реализации;
естественнее с точки зрения DFS;
дают очень сильные идеи для олимпиадных задач.

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

18.4 Офлайн-алгоритмы¶

Когда офлайн-подход полезен¶

Идея 1. Слияние структур данных по поддеревьям¶

Постановка задачи¶

Наивная идея¶

Структура данных в вершине¶

Как строить cnt[v]¶

Почему простое слияние может быть медленным¶

Приём small-to-large¶

Интуиция оценки O(n log n)¶

Пример¶

C++: small-to-large для подсчёта значений в поддереве¶

Что здесь важно¶

Замечания по структурам данных¶

Где ещё применяется small-to-large¶

Идея 2. Офлайн-нахождение LCA¶

Напоминание: что такое LCA¶

Общая идея алгоритма Тарьяна для LCA¶

Что хранит DSU¶

Ключевая мысль¶

Пошаговая схема алгоритма¶

Почему это работает¶

Небольшой пример¶

C++: офлайн LCA по Тарьяну¶

Как хранить запросы¶

Сложность¶

Сравнение с онлайн-методами¶

Бинарный подъём¶

Euler tour + RMQ¶

Тарьян офлайн¶

Когда какой подход выбирать¶

Выбирайте small-to-large, если¶

Выбирайте офлайн LCA Тарьяна, если¶

Важная методическая мысль¶

Краткое резюме¶

1. Слияние структур данных¶

2. Офлайн LCA Тарьяна¶

Что полезно потренировать¶

Дополнительное упражнение¶

Итог¶

Как строить `cnt[v]`¶

Интуиция оценки `O(n log n)`¶