e-maxx_algo

Рандомизированная куча

Рандомизированная куча (randomized heap) — это куча, которая за счёт применения генератора случайных чисел позволяет выполнять все необходимые операции за логарифмическое ожидаемое время.

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

Стандартный набор операций, определяемый для куч, следующий:

●Добавление элемента

●Нахождение минимума

●Извлечение минимума (удаление его из дерева и возврат его значения)

●Слияние двух куч (возвращается куча, содержащая элементы обеих куч; дубликаты не удаляются)

●Удаление произвольного элемента (при известной позиции в дереве)

Структура данных

Сразу опишем структуру данных, описывающую бинарную кучу:

struct tree {

T value;

tree * l, * r;

};

Выполнение операций

Нетрудно понять, что все операции над кучей сводятся к одной операции: слиянию двух куч в одну. Действительно, добавление элемента в кучу равносильно слиянию этой кучи с кучей, состоящей из единственного добавляемого элемента. Нахождение минимума вообще не требует никаких действий — минимумом просто является корень кучи. Извлечение минимума эквивалентно тому, что куча заменяется результатом слияния левого и правого поддерева корня. Наконец, удаление произвольного элемента аналогично удалению минимума:

всё поддерево с корнем в этой вершине заменяется результатом слияния двух поддеревьев-сыновей этой вершины.

Итак, нам фактически надо реализовать только операцию слияния двух куч, все остальные операции тривиально сводятся к этой операции.

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

мы должны объединить сыновей выбранной вершины с оставшейся кучей. Если мы по какому-то признаку выберем одного из двух сыновей, то тогда нам надо будет просто объединить поддерево в корне с этим сыном с кучей. Таким образом, мы снова пришли к операции слияния. Рано или поздно этот процесс остановится (на это понадобится, понятно, не более чем сумма высот куч).

Таким образом, чтобы достичь логарифмической асимптотики в среднем, нам надо указать способ выбора одного из двух сыновей с тем, чтобы в среднем длина проходимого пути получалась бы порядка логарифма от количества элементов в куче. Нетрудно догадаться, что производить этот выбор мы будем случайно, таким образом, реализация операции слияния получается такой:

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;

}

Здесь сначала проверяется, если хотя бы одна из куч пуста, то никаких действий по слиянию производить не надо. Иначе, мы делаем, чтобы куча была кучей с меньшим значением в корне (для чего обмениваем и , если надо). Наконец, мы считаем, что вторую кучу будем сливать с левым сыном корня кучи , поэтому мы случайным образом обмениваем левого и правого сыновей, а затем выполняем слияние левого сына и второй кучи.

Асимптотика

Введём случайную величину , обозначающую длину случайного пути от корня до листа (длина в

для исследования асимптотики алгоритма надо исследовать случайную величину .

Математическое ожидание

Утверждается, что математическое ожидание оценивается сверху логарифмом от числа вершин в этой куче:

Тогда справедливо:

что и требовалось доказать.

Превышение ожидаемой оценки

Докажем, что вероятность превышения полученной выше оценки мала:

для любой положительной константы .

что и требовалось доказать.

Асимптотика алгоритма

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

Более того, для любой положительной константы найдётся такая положительная константа , что вероятность того, что операция потребует больше чем операций, меньше (это в некотором смысле описывает

худшее поведение алгоритма).

Задача RMQ (Range Minimum Query - минимум на отрезке)

Дан массив A[1..N]. Поступают запросы вида (L, R), на каждый запрос требуется найти минимум в массиве A, начиная с позиции L и заканчивая позицией R.

Приложения

Помимо непосредственного применения в самых разных задачах, можно отметить следующие: ● Задача LCA (наименьший общий предок)

Решение

Задача RMQ решается с помощью структур данных.

Из описанных на сайте структур данных можно выбрать:

●Sqrt-декомпозиция - отвечает на запрос за O (sqrt (N)), препроцессинг за O (N). Преимущество в том, что это очень простая структура данных. Недостаток - асимптотика.

●Дерево отрезков - отвечает на запрос за O (log N), препроцессинг за O (N).

Преимущество - хорошая асимптотика. Недостаток - бОльший объём кода по сравнению с другими структурами данных.

●Дерево Фенвика - отвечает на запрос за O (log N), препроцессинг за O (N log N)

Преимущество - очень быстро пишется и работает тоже очень быстро. Но значительный недостаток - дерево Фенвика может отвечать только на запросы с L = 1, что для многих приложений неприменимо.

Примечание. "Препроцессинг" - это предварительная обработка массива A, фактически это построение структуры данных для данного массива.

Теперь предположим, что массив A может изменяться в процессе работы (т.е. также будут поступать запросы об изменении значения в некотором отрезке [L;R]). Тогда полученную задачу можно решить с помощью

Sqrt-декомпозиции и Дерева отрезков.

Нахождение наидлиннейшей возрастающей подпоследовательности

этой последовательности строго возрастающую подпоследовательность наибольшей длины.

Формально это выглядит следующим образом: требуется найти такую последовательность индексов , что:

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

Решение за : метод динамического программирования

Динамическое программирование — это весьма общая методика, позволяющая решать огромный класс задач. Здесь мы рассмотрим эту методику применительно к нашей конкретной задаче.

Научимся сначала искать длину наидлиннейшей возрастающей подпоследовательности, а восстановлением самой подпоследовательности займёмся чуть позже.

Динамическое программирование для поиска длины ответа

Для этого давайте научимся считать массив , где — это длина наидлиннейшей возрастающей подпоследовательности, оканчивающейся именно в элементе с индексом . Массив этот (он и есть —

уже подсчитаны. Тогда заметим, что у нас есть два варианта:

Объединяя эти два варианта в один, получаем окончательный алгоритм для вычисления :

Этот алгоритм — и есть сама динамика.

Реализация

Приведём реализацию описанного выше алгоритма, которая находит и выводит длину наидлиннейшей возрастающей подпоследовательности:

int d[MAXN]; // константа MAXN равна наибольшему возможному значению n

for (int i=0; i<n; ++i) { d[i] = 1;

for (int j=0; j<i; ++j) if (a[j] < a[i])

d[i] = max (d[i], 1 + d[j]);

}

с двоичным поиском

возрастающая подпоследовательность длины (а если таких чисел несколько — то наименьшее из них). Изначально мы полагаем , а все остальные элементы .

Считать эту динамику мы будем постепенно, обработав число , затем , и т.д. Приведём реализацию этой динамики за :

int d[MAXN]; d[0] = -INF;

for (int i=1; i<=n; ++i) d[i] = INF;

for (int i=0; i<n; i++)

for (int j=1; j<=n; j++)

if (d[j-1] < a[i] && a[i] < d[j]) d[j] = a[i];

Реализация за

Воспользовавшись стандартным в языке C++ алгоритмом двоичного поиска (который возвращает позицию первого элемента, строго большего данного), получаем такую простую реализацию:

int d[MAXN]; d[0] = -INF;

for (int i=1; i<=n; ++i) d[i] = INF;

for (int i=0; i<n; i++) {

int j = int (upper_bound (d.begin(), d.end(), a[i]) - d.begin()); if (d[j-1] < a[i] && a[i] < d[j])

d[j] = a[i];

}

Восстановление ответа

По такой динамике тоже можно восстановить ответ, для чего опять же помимо динамики также надо хранить массив "предков" — то, на элементе с каким индексом оканчивается оптимальная подпоследовательность длины

который должен стоять перед в оптимальной подпоследовательности.

Поддерживая эти два массива по ходу вычисления динамики, в конце будет нетрудно восстановить искомую подпоследовательность.

(Интересно отметить, что применительно к данной динамике ответ можно восстанавливать только так, через массивы предков — а без них восстановить ответ после вычисления динамики будет невозможно. Это один из редких случаев, когда к динамике неприменим альтернативный способ восстановления — без массивов предков).

Решение за : структуры данных

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

В самом деле, давайте вернёмся к самой первой динамике, где состоянием являлась просто текущая позиция.

Следовательно, если мы через обозначим такой массив, в который будем записывать значения динамики от чисел:

то получается, что всё, что нам надо уметь — это искать максимум на префиксе массива

: .

Задача поиска максимума на префиксах массива (с учётом того, что массив может меняться) решается многими стандартными структурами данных, например, деревом отрезков или деревом Фенвика.

Воспользовавшись любой такой структурой данных, мы получим решение за .

У этого способа решения есть явные недостатки: по длине и сложности реализации этот путь будет в любом случае хуже, чем описанная выше динамика за . Кроме того, если входные числа могут

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

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

Смежные задачи

Приведём здесь несколько задач, тесно связанных с задачей поиска наидлиннейшей возрастающей подпоследовательности.

Наидлиннейшая неубывающая подпоследовательность

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

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

Количество наидлиннейших возрастающих подпоследовательностей

По всей видимости, способ решения через динамику за к данной задаче применить невозможно.

Наименьшее число невозрастающих подпоследовательностей, покрывающих данную последовательность

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

Решение. Утверждается, что минимальное количество необходимых цветов равно длине наидлиннейшей возрастающей подпоследовательности.

Доказательство. Фактически, нам надо доказать двойственность этой задачи и задачи поиска наидлиннейшей возрастающей подпоследовательности.

Обозначим через длину наидлиннейшей возрастающей подпоследовательности, а через — искомое наименьшее число невозрастающих подпоследовательностей. Нам надо доказать, что .

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

Таким образом, в самом деле, , что и требовалось доказать.

Восстановление ответа. Утверждается, что само искомое разбиение на подпоследовательности можно искать жадно, т.е. идя слева направо и относя текущее число в ту подпоследовательность, которая сейчас заканчивается на минимальное число, больше либо равное текущему.

Задачи в online judges

K-ая порядковая статистика за O (N)

Пусть дан массив A длиной N и пусть дано число K. Задача заключается в том, чтобы найти в этом массиве K-ое по величине число, т.е. K-ую порядковую статистику.

Основная идея - использовать идеи алгоритма быстрой сортировки. Собственно, алгоритм несложный, сложнее доказать, что он работает в среднем за O (N), в отличие от быстрой сортировки.

Реализация в виде нерекурсивной функции:

template <class T>

T order_statistics (std::vector<T> a, unsigned n, unsigned k)

{

using std::swap;

for (unsigned l=1, r=n; ; )

{

if (r <= l+1)

{

//текущая часть состоит из 1 или 2 элементов -

//легко можем найти ответ

if (r == l+1 && a[r] < a[l]) swap (a[l], a[r]);

return a[k];

}

//упорядочиваем a[l], a[l+1], a[r] unsigned mid = (l + r) >> 1;

swap (a[mid], a[l+1]); if (a[l] > a[r])

swap (a[l], a[r]); if (a[l+1] > a[r])

swap (a[l+1], a[r]); if (a[l] > a[l+1])

swap (a[l], a[l+1]);

//выполняем разделение

//барьером является a[l+1], т.е. медиана среди a[l], a[l+1],

a[r]

unsigned

i = l+1, j = r;

const T

cur = a[l+1];

for (;;)

{

while (a[++i] < cur) ; while (a[--j] > cur) ; if (i > j)

break; swap (a[i], a[j]);

}

//вставляем барьер a[l+1] = a[j];

a[j] = cur;

//продолжаем работать в той части,

//которая должна содержать искомый элемент if (j >= k)

r = j-1; if (j <= k)

l = i;

}

}

Следует заметить, что в стандартной библиотеке C++ этот алгоритм уже реализован - он называется nth_element.