СНМ: различия между версиями
Глеб (обсуждение | вклад) |
|||
Строка 9: | Строка 9: | ||
Тогда, чтобы отвечать на $3$-ий запрос, нам достаточно возвращать корень дерева, в котором находится вершина $~-$ для этого надо подниматься в предка до тех пор, пока не дойдём до корня $~-$ у него предком будет он сам. | Тогда, чтобы отвечать на $3$-ий запрос, нам достаточно возвращать корень дерева, в котором находится вершина $~-$ для этого надо подниматься в предка до тех пор, пока не дойдём до корня $~-$ у него предком будет он сам. | ||
− | Чтобы реализовать $Merge(i, j)$, нам надо научиться объединять деревья. Вспомним, что в $GetComponentId$ нам нужно подниматься от вершины до корня. Значит, нам хотелось бы, чтобы эта величина была как можно меньше в среднем. Значит, надо следить за тем, чтобы деревья получались сбалансированными. Для этого будем хранить в каждой вершине $ | + | Чтобы реализовать $Merge(i, j)$, нам надо научиться объединять деревья. Вспомним, что в $GetComponentId$ нам нужно подниматься от вершины до корня. Значит, нам хотелось бы, чтобы эта величина была как можно меньше в среднем. Значит, надо следить за тем, чтобы деревья получались сбалансированными. Для этого будем хранить в каждой вершине $size(i) ~-$ количество вершин в поддереве. При $Merge(i, j)$ корневых деревьев у нас есть 2 варианта: подвесить $root(i)$ к $root(j)$ или наоборот. Выберем тот из вариантов, в котором получившееся дерево будет более сбалансированным. Для этого будем подвешивать '''лёгкое''' дерево '''тяжёлому''', а при равенстве будем подвешивать первое ко второму. |
Talk is cheap. Show me the code | Talk is cheap. Show me the code | ||
Строка 15: | Строка 15: | ||
vector<int> p; | vector<int> p; | ||
− | vector<int> | + | vector<int> size; |
void init(n) { | void init(n) { | ||
Строка 28: | Строка 28: | ||
*/ | */ | ||
− | + | size.resize(n, 1); | |
} | } | ||
Строка 49: | Строка 49: | ||
} | } | ||
− | if ( | + | if (size[root_i] < size[root_j]) { |
p[root_i] = root_j; | p[root_i] = root_j; | ||
− | + | size[root_j] += size[root_i]; | |
+ | } else { | ||
p[root_j] = root_i; | p[root_j] = root_i; | ||
− | + | size[root_i] += size[root_j]; | |
− | |||
− | |||
} | } | ||
} | } | ||
Строка 62: | Строка 61: | ||
===Лемма о ранговой эвристике=== | ===Лемма о ранговой эвристике=== | ||
− | Если $ | + | Если $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))$. Оказывается, можно и быстрее. | Итак, мы с вами научились строить структуру данных, в которых сложность каждого запроса составляет $O(log(n))$. Оказывается, можно и быстрее. | ||
Строка 84: | Строка 83: | ||
vector<int> p; | vector<int> p; | ||
− | vector<int> | + | vector<int> size; |
void init(n) { | void init(n) { | ||
Строка 97: | Строка 96: | ||
*/ | */ | ||
− | + | size.resize(n, 1); | |
} | } | ||
Строка 107: | Строка 106: | ||
return p[i] = GetRoot(p[i]); | return p[i] = GetRoot(p[i]); | ||
} | } | ||
+ | |||
void Merge(int i, int j) { | void Merge(int i, int j) { | ||
Строка 118: | Строка 118: | ||
} | } | ||
− | if ( | + | if (size[root_i] < size[root_j]) { |
p[root_i] = root_j; | p[root_i] = root_j; | ||
− | + | size[root_j] += size[root_i]; | |
+ | } else { | ||
p[root_j] = root_i; | p[root_j] = root_i; | ||
− | + | size[root_i] += size[root_j]; | |
− | |||
− | |||
} | } | ||
} | } |
Версия 16:29, 22 ноября 2019
Содержание
Задача:
Хотим реализовать структуру данных, которая поддерживает следующие операции:
- $init(n)$: создать $n$ множеств размера $1$: $0, 1, \dots, n-1$
- $Merge(i, j)$: слить множества, в которых сейчас лежат числа $i$ и $j$, в одно множество.
- $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];
}
}
Сложность $GetRoot$ (б/д)
Пусть нам поступаем $g$ запросов типа $GetRoot$. Тогда СНМ с обеими эвристиками выполнит их за суммарное время $O(g \times log^*(g))$ Что такое $log^*(x)$
Автор конспекта: Александр Гришутин
По всем вопросам пишите в telegram @rationalex