Алгоритмы C++
.pdf
Однако нетрудно убедиться в том, что все такие числа j получаются из i последовательными заменами самого
правого (самого младшего) нуля в двоичном представлении. Например, для i = 10 мы получим, что j = 11, 15, 31, 63 и т.д. Как ни странно, такой операции (замена самого младшего нуля на единицу) также соответствует очень простая формула:
H(X) = X | (X+1),
где | - это операция побитового логического "ИЛИ".
Реализация дерева Фенвика для суммы для одномерного случая
vector<int> t; int n;
void init (int nn)
{
n = nn; t.assign (n, 0);
}
int sum (int r)
{
int result = 0;
for (; r >= 0; r = (r & (r+1)) - 1) result += t[r];
return result;
}
void inc (int i, int delta)
{
for (; i < n; i = (i | (i+1))) t[i] += delta;
}
int sum (int l, int r)
{
return sum (r) - sum (l-1);
}
void init (vector<int> a)
{
init ((int) a.size());
for (unsigned i = 0; i < a.size(); i++) inc (i, a[i]);
}
Реализация дерева Фенвика для минимума для одномерного случая
Следует сразу заметить, что, поскольку дерево Фенвика позволяет найти значение функции в произвольном отрезке [0; R], то мы никак не сможем найти минимум на отрезке [L;R], где L > 0. Далее, все изменения значений должны происходить только в сторону уменьшения (опять же, поскольку никак не получится обратить функцию min).
Это значительные ограничения.
vector<int> t; int n;
const int INF = 1000*1000*1000;
void init (int nn)
{
n = nn;
t.assign (n, INF);
}
int getmin (int r)
{
int result = INF;
for (; r >= 0; r = (r & (r+1)) - 1) result = min (result, t[r]);
return result;
}
void update (int i, int new_val)
{
for (; i < n; i = (i | (i+1))) t[i] = min (t[i], new_val);
}
void init (vector<int> a)
{
init ((int) a.size());
for (unsigned i = 0; i < a.size(); i++) update (i, a[i]);
}
Реализация дерева Фенвика для суммы для двумерного случая
Как уже отмечалось, дерево Фенвика легко обобщается на многомерный случай.
vector <vector <int> > t; int n, m;
int sum (int x, int y)
{
int result = 0;
for (int i = x; i >= 0; i = (i & (i+1)) - 1)
for (int j = y; j >= 0; j = (j & (j+1)) - 1) result += t[i][j];
return result;
}
void inc (int x, int y, int delta)
{
for (int i = x; i < n; i = (i | (i+1)))
for (int j = y; j < m; j = (j | (j+1))) t[i][j] += delta;
}
для них равна O (alpha(N)), где alpha(N) - инверсия функции Аккермана:
alpha(N) = min { k : AK(1) >= N }, где
AK(J) = AK-1J+1(J) при K > 0, и A0(J) = J+1
Несколько первых значений функции alpha:
alpha(0)..alpha(2) = 0 alpha(3) = 1 alpha(4)..alpha(7) = 2 alpha(8)..alpha(2047) = 3
alpha(2048)..alpha(16512) = 4
Отсюда видно, что для всех мыслимых применений alpha(N) <= 4, а потому её можно считать константой, и приравнивать O (1).
Описание алгоритмов
Пусть элементы X - это некоторые числа. Вся структура данных хранится в виде двух массивов: P и Rank.
Массив P содержит предков, т.е. P[X] - это предок элемента X. Фактически, мы имеем древовидную структуру данных: двигаясь по предкам от любого элемента X, мы рано или поздно придём к представителю множества, к которому принадлежит X. В частности, если P[X] = X для некоторого X, то это означает, что X является представителем множества, к которому он принадлежит, и, очевидно, X является корнем дерева.
Массив Rank хранит ранги представителей, т.е. его значения имеют смысл только для элементовпредставителей. Ранг некоторого элемента-представителя X - это верхняя граница его высоты в его дереве. Ранги используются в качестве эвристики в операции Union.
Теперь рассмотрим реализацию операций:
●MakeSet (X)
Эта операция очень проста - мы указываем, что P[X] = X, а ранг X равен 1.
●FindSet (X)
Будем двигаться от X по предкам, и рано или поздно мы найдём представителя. Однако важный момент -
мы одновременно применяем следующую эвристику: у каждого элемента, который мы проходим, мы также
исправляем P, указывая его сразу на найденного представителя. Т.е. фактически операция FindSet двухпроходная: на первом проходе мы ищем представителя, а на втором исправляем значения P.
● Union (X, Y)
Сначала мы заменяем элементы X и Y на представителей их множеств, просто вызывая функцию FindSet. Мы объединяем два множества, присваивая P[X] = Y или P[Y] = X. Однако выбор - что чему присваивается - осуществляется с помощью эвристики. Если ранги элементов X и Y отличны, то мы делаем корень с бо'льшим рангом родительским по отношению к корню с меньшим рангом. Если же ранги обоих элементов совпадают, то мы выбираем родителя произвольным образом, и увеличиваем его ранг на 1.
Следует ещё раз подчеркнуть важность двух эвристик, использованных в операциях FindSet и Union. Без них асимптотика этих операций значительно ухудшится (до линейного вместо константного времени).
Реализация
vector<int> p, rank;
void init (int max_n)
{
p.resize (max_n);
for (int i=0; i<max_n; ++i) p[i] = i;
rank.resize (max_n);
}
void make_set (int x)
{
p[x] = x; rank[x] = 0;
}
int find_set (int x)
{
if (x == p[x]) return x; return p[x] = find_set (p[x]);
}
void unite (int x, int y)
{
x = find_set (x); y = find_set (y);
if (rank[x] > rank[y]) p[y] = x;
else
{
p[x] = y;
if (rank[x] == rank[y]) ++rank[y];
}
}
Рандомизация
Представленные выше алгоритмы были детерминированными. Однако, в некоторых случаях имеет смысл сделать операцию Union рандомизированной - заменить эвристику по рангу на случайный выбор родительского узла. Тесты показывают, что такая реализация нисколько не отстаёт от детерминированного варианта, однако пишется и запоминается ещё легче:
vector<int> p;
void init (int max_n)
{
p.resize (max_n);
for (int i=0; i<max_n; ++i) p[i] = i;
}
void make_set (int x)
{
p[x] = x;
}
int find_set (int x)
{
if (x == p[x]) return x; return p[x] = find_set (p[x]);
}
void unite (int x, int y)
{
x = find_set (x); y = find_set (y); if (rand() & 1)
p[y] = x;
else
p[x] = y;
}
Дерево отрезков
Дерево отрезков - структура данных, которая позволяет реализовать за O (log N) операции следующего типа: нахождение суммы/минимума элементов массива в заданном отрезке (A[L..R], где L и R - это параметры запроса), изменение одного элемента массива, изменение/прибавление элементов на отрезке (A[L..R]). При этом объём дополнительно используемой памяти составляет O (N), или, если быть точным, не более 4 N.
Описание
Для простоты описания будем считать, что мы строим дерево отрезков для суммы.
Построим бинарное дерево T следующим образом. Корень дерева будет храниться в элементе T[1]. Он
будет содержать сумму элементов A[0..N-1], т.е. всего массива. Левый сын корня будет храниться в элементе T[2]
и содержать сумму первой половины массива A: A[0..N/2], а правый сын - в элементе T[3] и содержать сумму элементов A[N/2+1..N-1]. В общем случае, если T[i]-ый элемент содержит сумму элементов с L-го по R-ый, то его левым сыном будет элемент T[i*2] и содержать сумму A[L..(L+R)/2], а его правым сыном будет T[i*2+1] и содержать сумму A[(L+R)/2+1.. R]. Исключение, разумеется, составляют листья дерева - вершины, в которых L = R.
Далее, нетрудно заметить, что это дерево будет содержать 4 N элементов (а высота дерева будет порядка O (log N)). Поскольку значение в каждом элементе дерева однозначно определяется значениями в его сыновьях, то каждый элемент вычисляется за O (1), а всё дерево строится за O (N).
Рассмотрим теперь операцию суммы на некотором отрезке [L; R]. Мы встаём в корень дерева (i=1), и рекурсивно движемся вниз по этому дереву. Если в какой-то момент оказывается, что L и R совпадают с границами отрезка текущего элемента, то мы просто возвращаем значение текущего элемента T. Иначе, если отрезок [L; R] целиком попадает в отрезок левого или правого сына текущего элемента, то мы рекурсивно вызываем себя из этого сына и найденное значение возвращаем. Наконец, если отрезок [L; R] частично принадлежит и отрезку левого сына, и отрезку правого сына, то делим отрезок [L; R] на два отрезка [L; M] и [M+1; R] так, чтобы первый отрезок
целиком принадлежал отрезку левого сына, а второй отрезок - отрезку правого сына, и рекурсивно вызываем себя и от первого, и от второго отрезков, возвращая сумму найденных сумм. В итоге вся операция суммирования работает за
O (log N).
Теперь рассмотрим операцию изменения значения некоторого элемента с индексом K. Будем спускаться по дереву от корня, ища тот лист, который содержит значение элемента A[K]. Когда мы найдём этот элемент, просто изменим соответствующее значение в массиве T и будем подниматься от текущего элемента обратно к
корню, пересчитывая текущие значения T. Понятно, что таким образом мы изменим все значения в дереве, которые
нужно изменить. Итого асимптотика O (log N).
Наконец, рассмотрим операцию изменения на отрезке. Для реализации этой операции нам понадобится немного модифицировать дерево. Пусть каждый элемент дерева, помимо суммы, будет содержать значение Val[i]: если все элементы массива A в текущем отрезке равны друг другу, то Val[i] будет содержать это значение, а иначе он будет содержать некое значение "неопределённость". Изначально его можно просто заполнить
значениями "неопределённость". А при выполнении операции изменения на отрезке мы будем спускаться по дереву, как в вышеописанном алгоритме суммирования, и если в какой-то момент L и R совпали с границами текущего отрезка, то мы присвоим Val[i] новое значение, которое мы хотим записать. Понятно, что теперь надо будет
модифицировать операцию суммирования - если она в какой-то момент встречает Val[i], отличное от "неопределённости", то она прекращает спуск по дереву и сразу возвращает нужное значение - действительно, результат уже определён значением Val[i], а вот если мы продолжим спуск, то уже будем считывать неправильные, старые значения.
Операция прибавления на отрезке реализуется подобным образом, но несколько проще. В каждом элементе мы храним Add[i] - значение, которое нужно прибавить ко всем элементам этого отрезка. Операция прибавления на отрезке будет модифицировать эти значения, а операция суммирования - просто прибавлять к ответу
все встретившиеся значения Add.
Реализация
Например, рассмотрим дерево отрезков для суммы с одиночной модификацией:
vector<long long> t; int n;
void build (const vector<int> & a, int i = 1, int l = 0, int r = n-1) { if (i == 1)
t.resize (n*4 + 1); if (l == r)
t[i] = a[l];
else {
int m = (l + r) / 2; build (a, i*2, l, m); build (a, i*2+1, m+1, r); t[i] = t[i*2] + t[i*2+1];
}
}