Алгоритмы C++
.pdf
объединить дерево t1 с новой вершиной; для этого достаточно вызвать merge (t1, t1, new_item) (нетрудно убедиться в том, что все предусловия для merge выполнены). Наконец, объединим два дерева t1 и t2 обратно в дерево t -
вызовом merge (t, t1, t2).
●Удаление элемента.
Здесь всё ещё проще: достаточно найти удаляемый элемент, а затем выполнить merge для его сыновей l и r, и поставить результат объединения на место вершины t. Фактически, удаление из неявного декартова дерева не отличается от удаления из обычного декартова дерева.
●Сумма/минимум и т.п. на отрезке.
Во-первых, для каждой вершины создадим дополнительное поле f в структуре item, в котором будет храниться значение целевой функции для поддерева этой вершины. Такое поле легко поддерживать, для этого надо поступить аналогично поддержке размеров cnt (создать функцию, вычисляющую значение этого поля, пользуясь его значениями для сыновей, и вставить вызовы этой функции в конце всех функций, меняющих дерево). Во-вторых, нам надо научиться отвечать на запрос на произвольном отрезке [A;B]. Научимся выделять из дерева
его часть, соответствующую отрезку [A;B]. Нетрудно понять, что для этого достаточно сначала вызвать split (t, t1, t2, A), а затем split (t2, t2, t3, B-A+1). В результате дерево t2 и будет состоять из всех элементов в отрезке [A;B], и только них. Следовательно, ответ на запрос будет находиться в поле f вершины t2. После ответа на запрос дерево
надо восстановить вызовами merge (t, t1, t2) и merge (t, t, t3).
●Прибавление/покраска на отрезке.
Здесь мы поступаем аналогично предыдущему пункту, но вместо поля f будем хранить поле add, которое и будет содержать прибавляемую величину (или величину, в которую красят всё поддерево этой вершины).
Перед выполнением любой операции эту величину add надо "протолкнуть" - т.е. соответствующим образом изменить t- l->add и t->r->add, а у себя значение add снять. Тем самым мы добьёмся того, что ни при каких изменениях
дерева информация не будет потеряна.
●Переворот на отрезке.
Этот пункт почти аналогичен предыдущему - нужно ввести поле bool rev, которое ставить в true, когда
требуется произвести переворот в поддереве текущей вершины. "Проталкивание" поля rev заключается в том, что мы обмениваем местами сыновья текущей вершины, и ставим этот флаг для них.
Реализация. Приведём для примера полную реализацию неявного декартова дерева с переворотом на отрезке. Здесь для каждой вершины также хранится поле value - собственно значение элемента, стоящего в массиве на текущей позиции. Приведена также реализация функции output(), которая выводит массив, соответствующий текущему состоянию неявного декартова дерева.
typedef struct item * pitem; struct item {
int prior, value, cnt; bool rev;
pitem l, r;
};
int cnt (pitem it) {
return it ? it->cnt : 0;
}
void upd_cnt (pitem it) { if (it)
it->cnt = cnt(it->l) + cnt(it->r) + 1;
} |
|
|
void push (pitem it) { |
|
|
if (it && |
it->rev) { |
|
it->rev = false; |
||
swap (it->l, it->r); |
||
if (it->l) |
it->l->rev ^= true; |
|
if (it->r) |
it->r->rev ^= true; |
|
} |
|
|
} |
|
|
void merge (pitem |
& t, pitem l, pitem r) { |
|
push (l); |
|
|
push (r); |
!r) |
|
if (!l || |
|
|
t |
= l ? l : r; |
|
else if (l->prior > r->prior)
merge (l->r, l->r, r), t = l;
else
merge (r->l, l, r->l), t = r; upd_cnt (t);
}
void split (pitem t, pitem & l, pitem & r, int key, int add = 0) { if (!t)
return void( l = r = 0 ); push (t);
int cur_key = add + cnt(t->l); if (key <= cur_key)
split (t->l, l, t->l, key, add), r = t;
else
split (t->r, t->r, r, key, add + 1 + cnt(t->l)), l = t; upd_cnt (t);
}
void reverse (pitem t, int l, int r) { pitem t1, t2, t3;
split (t, t1, t2, l); split (t2, t2, t3, r-l+1); t2->rev ^= true;
merge (t, t1, t2); merge (t, t, t3);
}
void output (pitem t) { if (!t) return; push (t);
output (t->l);
printf ("%d ", t->value); output (t->r);
}
Модификация стека и очереди для извлечения минимума за O (1)
Здесь мы рассмотрим три задачи: модифицирование стека с добавлением извлечения наименьшего элемента за O (1), аналогичное модифицирование очереди, а также применение их к задаче нахождения минимума во всех подотрезках фиксированной длины данного массива за O (N).
Модификация стека
Требуется добавить возможность извлечения минимума из стека за O (1), сохранив такой же асимптотику добавления и удаления элементов из стека.
Для этого будем хранить в стеке не сами элементы, а пары: элемент и минимум в стеке, начиная с этого элемента и ниже. Иными словами, если представить стек как массив пар, то
stack[i].second = min { stack[j].first } j = 0..i
Понятно, что тогда нахождение минимума во всём стеке будет заключаться просто во взятии значения stack.top().second.
Также очевидно, что при добавлении нового элемента в стек величина second будет равна min (stack.top(). second, new_element). Удаление элемента из стека ничем не отличается от удаления из обычного стека, поскольку удаляемый элемент никак не мог повлиять на значения second для оставшихся элементов.
Реализация:
stack< pair<int,int> > st;
● Добавление элемента:
int minima = st.empty() ? new_element : min (new_element, st.top().second); st.push (make_pair (new_element, minima));
● Извлечение элемента:
int result = st.top().first; st.pop();
● Нахождение минимума:
minima = st.top().second;
Модификация очереди. Способ 1
Здесь рассмотрим простой способ модификации очереди, но имеющий тот недостаток, что модифицированная очередь реально может хранить не все элементы (т.е. при извлечении элемента из очереди нам надо будет знать значение элемента, который мы хотим извлечь). Ясно, что это весьма специфичная ситуация (обычно очередь нужна как раз для того, чтобы узнавать очередной элемент, а не наоборот), однако этот способ привлекателен своей простотой. Также этот метод применим к задаче о нахождении минимума в подотрезках (см. ниже).
Ключевая идея заключается в том, чтобы реально хранить в очереди не все элементы, а только нужные нам для определения минимума. А именно, пусть очередь представляет собой неубывающую последовательность чисел (т.е.
вголове хранится наименьшее значение), причём, разумеется, не произвольную, а всегда содержащую минимум. Тогда минимум во всей очереди всегда будет являться первым её элементом. Перед добавлением нового элемента
вочередь достаточно произвести "срезку": пока в хвосте очереди находится элемент, больший нового элемента, будем удалять этот элемент из очереди; затем добавим новый элемент в конец очереди. Тем самым мы, с одной стороны, не нарушим порядка, а с другой стороны, не потеряем текущий элемент, если он на каком-либо последующем шаге окажется минимумом. Но при извлечении элемента из головы очереди его там, вообще говоря, может уже не оказаться - наша модифицированная очередь могла выкинуть этот элемент в процессе перестроения. Поэтому при удалении элемента нам надо знать значение извлекаемого элемента - если элемент с этим значением находится в голове очереди, то извлекаем его; иначе просто ничего не делаем.
Рассмотрим реализацию вышеописанных операций:
deque<int> q;
● Нахождение минимума:
current_minimum = q.front();
● Добавление элемента:
while (!q.empty() && q.back() > added_element) q.pop_back();
q.push_back (added_element);
● Извлечение элемента:
if (!q.empty() && q.front() == removed_element) q.pop_front();
Понятно, что в среднем время выполнения всех этих операций есть O (1).
Модификация очереди. Способ 2
Рассмотрим здесь другой способ модификации очереди для извлечения минимума за O (1), который несколько более сложен для реализации, однако лишён основного недостатка предыдущего метода: все элементы очереди реально сохраняются в ней, и, в частности, при извлечении элемента не требуется знать его значение.
Идея заключается в том, чтобы свести задачу к задаче на стеках, которая уже была нами решена. Научимся моделировать очередь с помощью двух стеков.
Заведём два стека: s1 и s2; разумеется, имеются в виду стеки, модифицированные для нахождения минимума за O
(1). Добавлять новые элементы будет всегда в стек s1, а извлекать элементы - только из стека s2. При этом, если при попытке извлечения элемента из стека s2 он оказался пустым, просто перенесём все элементы из стека s1 в стек
s2 (при этом элементы в стеке s2 получатся уже в обратном порядке, что нам и нужно для извлечения элементов; стек s1 же станет пустым). Наконец, нахождение минимума в очереди будет фактически заключаться в нахождении минимума из минимума в стеке s1 и минимума в стеке s2.
Тем самым, мы выполняем все операции по-прежнему за O (1) (по той простой причине, что каждый элемент в худшем случае 1 раз добавляется в стек s1, 1 раз переносится в стек s2 и 1 раз извлекается из стека s2).
Реализация:
stack< pair<int,int> > s1, s2;
● Нахождение минимума:
if (s1.empty() || s2.empty())
current_minimum = s1.empty ? s2.top().second : s1.top().second;
else
current_minimum = min (s1.top().second, s2.top().second);
● Добавление элемента:
int minima = s1.empty() ? new_element : min (new_element, s1.top().second); s1.push (make_pair (new_element, minima));
● Извлечение элемента:
if (s2.empty())
while (!s1.empty()) {
int element = s1.top().first; s1.pop();
int minima = s2.empty() ? element : min (element, s2.top
().second);
s2.push (make_pair (element, minima));
}
result = s2.top().first; s2.pop();
Задача нахождения минимума во всех подотрезках фиксированной длины данного массива
Пусть дан массив A длины N, и дано число M ≤ N. Требуется найти минимум в каждом подотрезке длины M данного массива, т.е. найти:
min A[i], |
min A[i], |
min A[i], |
..., |
min A[i] |
0≤i≤M-1 |
1≤i≤M |
2≤i≤M+1 |
|
N-M≤i≤N-1 |
|
|
|
|
|
Решим эту задачу за линейное время, т.е. O (N).
Для этого достаточно завести очередь, модифицированную для нахождения минимума за O (1), что было
рассмотрено нами выше, причём в данной задаче подойдёт любой из двух методов реализации такой очереди. Далее решение уже понятно: добавим в очередь первые M элементов массива, найдём в ней минимум и выведем его, затем добавим в очередь следующий элемент, и извлечём из неё первый элемент массива, снова выведем минимум, и т.д. Поскольку все операции с очередью выполняются в среднем за константное время, то и асимптотика всего алгоритма получится O (N).
Стоит заметить, что реализация модифицированной очереди первым методом проще, однако для неё, вероятно, потребуется хранить весь массив (поскольку на i-ом шаге потребуется знать i-ый и (i-M)-ый элементы
массива). При реализации очереди вторым методом массив A хранить явно не понадобится - только узнавать очередной, i-ый элемент массива.
Нетрудно понять, что все операции над кучей сводятся к одной операции: слиянию двух куч в одну. Действительно, добавление элемента в кучу равносильно слиянию этой кучи с кучей, состоящей из единственного добавляемого элемента. Нахождение минимума вообще не требует никаких действий — минимумом просто является корень кучи. Извлечение минимума эквивалентно тому, что куча заменяется результатом слияния левого и правого поддерева корня. Наконец, удаление произвольного элемента аналогично удалению минимума:
всё поддерево с корнем в этой вершине заменяется результатом слияния двух поддеревьев-сыновей этой вершины.
Итак, нам фактически надо реализовать только операцию слияния двух куч, все остальные операции тривиально сводятся к этой операции.
Пусть даны две кучи |
и |
, требуется вернуть их объединение. Понятно, что в корне каждой из этих куч находятся |
их минимумы, поэтому в корне результирующей кучи будет находиться минимум из этих двух значений. Итак, мы сравниваем, в корне какой из куч находится меньшее значение, его помещаем в корень результата, а теперь
мы должны объединить сыновей выбранной вершины с оставшейся кучей. Если мы по какому-то признаку выберем одного из двух сыновей, то тогда нам надо будет просто объединить поддерево в корне с этим сыном с кучей. Таким образом, мы снова пришли к операции слияния. Рано или поздно этот процесс остановится (на это понадобится, понятно, не более чем сумма высот куч).
Таким образом, чтобы достичь логарифмической асимптотики в среднем, нам надо указать способ выбора одного из двух сыновей с тем, чтобы в среднем длина проходимого пути получалась бы порядка логарифма от количества элементов в куче. Нетрудно догадаться, что производить этот выбор мы будем случайно, таким образом, реализация операции слияния получается такой:
tree * merge (tree * t1, tree * t2) { if (!t1 || !t2)
return t1 ? t1 : t2;
if (t2->value < t1->value) swap (t1, t2);
if (rand() & 1)
swap (t1->l, t1->r); t1->l = merge (t1->l, t2); return t1;
}
Здесь сначала проверяется, если хотя бы одна из куч пуста, то никаких действий по слиянию производить не надо.
Иначе, мы делаем, чтобы куча |
была кучей с меньшим значением в корне (для чего обмениваем |
и , если |
|
надо). Наконец, мы считаем, что вторую кучу |
будем сливать с левым сыном корня кучи , поэтому мы |
||
случайным образом обмениваем левого и правого сыновей, а затем выполняем слияние левого сына и второй кучи.