СНМ

Задача

Хотим реализовать структуру данных, которая поддерживает следующие операции:

1. $init(n)$: создать $n$ множеств размера $1$: $0, 1, \dots, n-1$
2. $Merge(i, j)$: слить множества, в которых сейчас лежат числа $i$ и $j$, в одно множество.
3. $GetComponentId(i)$: выдать идентификатор множества, в котором лежит число $i$. Разумеется, мы хотим, чтобы для всех чисел в одном множестве ответ был одинаковый.

Реализуем эту структуру с помощью леса из корневых деревьев $~-$ каждый элемент будет в нём представлять из себя вершину и каждая вершина будет знать своего предка в текущем своём дереве. у вершины-корня положим предком её саму. Изначально (после $init$-а) каждая вершина будет являться деревом размера $1$.

Тогда, чтобы отвечать на $3$-ий запрос, нам достаточно возвращать корень дерева, в котором находится вершина $~-$ для этого надо подниматься в предка до тех пор, пока не дойдём до корня $~-$ у него предком будет он сам.

Ранговая эвристика

Чтобы реализовать $Merge(i, j)$, нам надо научиться объединять деревья. Вспомним, что в $GetComponentId$ нам нужно подниматься от вершины до корня. Значит, нам хотелось бы, чтобы эта величина была как можно меньше в среднем. Значит, надо следить за тем, чтобы деревья получались сбалансированными. Для этого будем хранить в каждой вершине $size(i) ~-$ количество вершин в поддереве. При $Merge(i, j)$ корневых деревьев у нас есть 2 варианта: подвесить $root(i)$ к $root(j)$ или наоборот. Выберем тот из вариантов, в котором получившееся дерево будет более сбалансированным. Для этого будем подвешивать лёгкое дерево тяжёлому, а при равенстве будем подвешивать первое ко второму.

Talk is cheap. Show me the code

vector<int> p;
vector<int> size;

void init(n) {
  p.resize(n);
  p.iota(p.begin(), p.end(), 0);
  /* equivalent to
   *
   * for (int i = 0; i < n; ++i) {
   *   p[i] = i;
   * }
   *
   */
  
  size.resize(n, 1);
}

int GetRoot(int i) {
  while (p[i] != i) {
    i = p[i];
  }

  return i;
}

void Merge(int i, int j) {
  int root_i = GetRoot(i);
  int root_j = GetRoot(j);

  // если вершины лежат в одном дереве
  // то можно ничего не делать
  if (root_i == root_j) {
    return;  
  }

  if (size[root_i] < size[root_j]) {
    p[root_i] = root_j;
    size[root_j] += size[root_i];
  } else {
    p[root_j] = root_i;
    size[root_i] += size[root_j];
  }
}

Лемма о ранговой эвристике

Если $size(v) = s$, то в самом длинном пути от $v$ до листа (вниз по дереву) не более $log_2(s)$ рёбер.

Доказательство

Будем доказывать индукцией по $s$.

База

$s = 1$. Дерево состоит из 1 вершины, $log_2(1) = 0$, значит, база верна.

Шаг

Дерево ранга $s$ мы получаем при объединении двух деревьев ранга $s_1$ и $s_2$ ($s_1 + s_2 = s)$. Пусть $s_2 > s_1$ В каждом из них, по предположению индукции, самый длинный путь содержит $log_2(s_i)$ рёбер. Так как мы подвешиваем лёгкое дерево к тяжёлому, самый длинный путь в получившемся дереве будет иметь длину $max(\underbrace{log_2(s_2)}_\text{самый длинный путь в тяжёлом дереве}, \underbrace{log_2(s_1)}_\text{самый длинный путь в лягком дереве} + \underbrace{1}_\text{ребро, за которое подвешиваем лёгкое к тяжёлому}) \leq log_2(s1+s2) = log_2(s) $

Итак, мы с вами научились строить структуру данных, в которых сложность каждого запроса составляет $O(log(n))$. Оказывается, можно и быстрее.

Сжатие путей

Идея: если в какой-то момент мы узнали, что $root(v) = r$, то можно после этого переподвесить $v$ к $r$, не нарушив свойств нашей структуры. Более того, у всех вершин $u$ на пути от $v$ до $r$, $root(u) = r$, и их тоже можно подвесить к $r$, таким образом сократив время ответа на дальнейшие запросы $GetRoot(u)$. Эта эвристика носит название эвристики о сжатии путей.

Эта на первый взгляд непростая эвристика оказывается на удивлении лаконичной в смысле кода.

Итоговый код, с обеими эвристиками:

vector<int> p;
vector<int> size;

void init(n) {
  p.resize(n);
  p.iota(p.begin(), p.end(), 0);
  /* equivalent to
   *
   * for (int i = 0; i < n; ++i) {
   *   p[i] = i;
   * }
   *
   */
  
  size.resize(n, 1);
}

int GetRoot(int i) {
  if (p[i] == i) {
    return i;
  }

  return p[i] = GetRoot(p[i]);
}


void Merge(int i, int j) {
  int root_i = GetRoot(i);
  int root_j = GetRoot(j);

  // если вершины лежат в одном дереве
  // то можно ничего не делать
  if (root_i == root_j) {
    return;  
  }

  if (size[root_i] < size[root_j]) {
    p[root_i] = root_j;
    size[root_j] += size[root_i];
  } else {
    p[root_j] = root_i;
    size[root_i] += size[root_j];
  }
}

Амортизированная стоимость $Get$

Проанализируем асимптотику операции $Get$ в случае, если мы применяем обе эвристики. Пусть произошло $g$ операций типа $Get$ и $m$ операций типа $Merge$, причём $g \geq m$. Тогда суммарное время работы всех $Get$ есть $O(g log^*(m))$ (или, что то же самое, амортизированная стоимость одного $Get$ есть $O(log^*(m))$ ( Что такое $\log^*(x)$ ).

Обозначим $d(v) ~-$ длину самого длинного пути вниз от вершины $v$.

Разобьём все операции $Get(v)$ на 3 типа:

1. $v ~-$ корень или ребёнок корня в своём дереве. Таких операций будет не более $g$.
2. $d(p(v)) \leq C ^ {d(v)}$, где $C$ ~- некоторая констатнта, которую мы подберём позже. Такие запросы мы назовём быстро растущими, а ребро $(v, p(v)) ~-$ лёгким.
3. $d(p(v)) < C ^ {d(v)}$ $~-$ такие запросы мы назовём медленно растущими, а соответствующее ребро $~-$ тяжёлым.

На запросы первого типа мы ответим суммарно за $O(g)$.

Проанализируем быстро растущие запросы. Каждый раз в них $d(v)$ изменяется на $C^{d(v)}$. Поскольку $C$ не может быть больше $log_2(m)$, каждая из этих операций выполнится за $O(log^*_C(log_2(m))) = O(log^*(m))$.

Лемма

Число вершин с $d(v) = i$ не превосходит $\frac{m}{2^i}$.

Доказательство этого утверждения (разумеется, по индукции) оставляется в качестве упражнения читателю.

Проанализируем запросы 3 типа. Из леммы выше следует, что суммарное количество операций в таких вызовах равно

$$ \sum_{d=0}^{log_2(g)} \sum_{u: d(u) = u} C^d = \sum_{d=0}^{log_2(g)} C^d \cdot \frac{m}{2^d} = m \cdot \sum_{d=0}^{log_2(g)} \frac{C}{2} ^ d $$

Теперь, если мы хотим, чтобы получившееся выражение было $O(m)$, нужно взять $C \in (e^\frac{1}{e}, 2)$.

Итак, мы получили, что суммарное время работы всех $Get$ есть $O(g) + O(g \cdot \log^*(m)) + O(m) = O(g \cdot \log^*(m))$ (поскольку мы предположили, что $g \geq m$).

Асимптотика с обеими эвристиками (б/д)

Пусть нам поступаем $g$ запросов типа $GetRoot$ и $m$ запросов типа $Merge$, причём $g \leq n$. Тогда СНМ с обеими эвристиками выполнит их за суммарное время $O((g+m) \times \alpha(g+m))$ Что такое $\alpha(x)$

На практике эта теорема означает, что суммарное количество операций будет не более, чем в 5 раз больше, чем число запросов.

---

Автор конспекта: Александр Гришутин

По всем вопросам пишите в telegram @rationalex