e-maxx_algo

Sqrt-декомпозиция

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

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

Сначала мы опишем структуру данных для одного из простейших применений этой идеи, затем покажем, как обобщать её для решения некоторых других задач, и, наконец, рассмотрим несколько иное применение этой идеи:

разбиение входных запросов на sqrt-блоки.

Структура данных на основе sqrt-декомпозиции

сможет находить сумму элементов для произвольных и за операций.

Описание

Основная идея sqrt-декомпозиции заключается в том, что сделаем следующий предпосчёт: разделим массив на блоки длины примерно , и в каждом блоке заранее предпосчитаем сумму элементов в нём.

Можно считать, что длина одного блока и количество блоков равны одному и тому же числу — корню из , округлённому вверх:

тогда массив разбивается на блоки примерно таким образом:

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

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

придётся произвести суммирование тривиальным алгоритмом.

Иллюстрация (здесь через обозначен номер блока, в котором лежит , а через — номер блока, в котором лежит ):

в этом случае надо просто просуммировать элементы с по )

Тем самым мы экононим значительное количество операций. Действительно, размер каждого из "хвостов", очевидно, не превосходит длины блока , и количество блоков также не превосходит . Поскольку мы выбирали , то

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

Реализация

Приведём сначала простейшую реализацию:

//входные данные int n; vector<int> a (n);

//предпосчёт

int len = (int) sqrt (n + .0) + 1; // и размер блока, и количество блоков vector<int> b (len);

for (int i=0; i<n; ++i) b[i / len] += a[i];

// ответ на запросы for (;;) {

int l, r; // считываем входные данные - очередной запрос int sum = 0;

for (int i=l; i<=r; )

if (i % len == 0 && i + len - 1 <= r) {

// если i указывает на начало блока, целиком лежащего

в [l;r]

sum += b[i / len]; i += len;

}

else {

sum += a[i]; ++i;

}

}

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

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

if (c_l == c_r)

for (int i=l; i<=r; ++i) sum += a[i];

else {

for (int i=l, end=(c_l+1)*len-1; i<=end; ++i) sum += a[i];

for (int i=c_l+1; i<=c_r-1; ++i) sum += b[i];

for (int i=c_r*len; i<=r; ++i) sum += a[i];

}

Другие задачи

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

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

Аналогичным образом sqrt-декомпозицию можно применять и для множества других подобных задач:

нахождение количества нулевых элементов, первого ненулевого элемента, подсчёта количества определённых

элементов, и т.д.

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

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

будет выполняться за , а запрос отдельного элемента — за .

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

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

Можно привести пример и других задач, к которым можно применить sqrt-декомпозицию. Например, можно решать задачу о поддержании множества чисел с возможностью добавления/удаления чисел, проверки числа на принадлежность множеству, поиск -го по порядку числа. Для решения этой задачи надо хранить числа в отсортированном порядке, разделёнными на несколько блоков по чисел в каждом. При добавлении или

удалении числа надо будет производить "перебалансировку" блоков, перебрасывая числа из начал/концов одних блоков в начала/концы соседних блоков.

Sqrt-декомпозиция входных запросов

Рассмотрим теперь совершенно иное применение идеи об sqrt-декомпозиции.

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

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

Конкретная задача может быть весьма сложной, и "честное" её решение (которое считывает один запрос, обрабатывает его, изменяя состояние системы, и возвращает ответ) может быть технически сложным или вовсе быть не по силам для решающего. С другой стороны, решение "оффлайнового" варианта задачи, т.е. когда отсутствуют модифицирующие операции, а имеются только лишь запрашивающие запросы — часто оказывается

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

обрабатывать модифицирующие запросы.

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

"оффлайнового" варианта задачи по состоянию данных на момент начала этого блока.

Теперь будем по очереди брать запросы из текущего блока и обрабатывать каждый из них. Если текущий запрос

— модифицирующий, то пропустим его. Если же текущий запрос — запрашивающий, то обратимся к структуре данных для оффлайнового варианта задачи, но предварительно учтя все модифицирующие запросы в текущем блоке. Такое учитывание модифицирующих запросов бывает возможным далеко не всегда, и

оно должно происходить достаточно быстро — за время или немного хуже; обозначим это время через .

Поскольку приведённые выше рассуждения слишком абстрактны, приведём несколько примеров задач, к которым применима такая sqrt-декомпозиция.

Пример задачи: прибавление на отрезке

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

Итак, разобьём входные запросы на блоки по (где — число запросов). В начале первого блока запросов

текущий запрос — запрос прибавления, то пока пропускаем его. Если же текущий запрос — запрос чтения значения

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

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

Таким образом, итоговая асимптотика решения составит .

Пример задачи: disjoint-set-union с разделением

Есть неориентированный граф с вершинами и рёбрами. Поступают запросы трёх видов: добавить ребро

, удалить ребро , и проверить, связаны или нет вершины и путём.

Если бы запросы удаления отсутствовали, то решением задачи была бы известная структура данных disjoint-set- union (система непересекающихся множеств). Однако при наличии удалений задача значительно усложняется.

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

Как мы теперь должны отвечать на очередной запрос из текущего блока? Наша система непересекающихся множеств "знает" обо всех рёбрах, кроме тех, что добавляются/удаляются в текущем блоке. Однако удаления из dsu нам делать уже не надо — мы заранее удалили все такие рёбра из графа. Таким образом, всё, что может быть — это дополнительные, добавляющиеся рёбра, которых может быть максимум штук.

Следовательно, при ответе на текущий запрашивающий запрос мы можем просто пустить обход в ширину по компонентам связности dsu, который отработает за , поскольку у нас в рассмотрении будут только

рёбер.

Оффлайновые задачи на запросы на подотрезках массива и универсальная sqrt-эвристика для них

Рассмотрим ещё одну интересную вариацию идеи sqrt-декомпозиции.

Пусть у нас есть некоторая задача, в которой есть массив чисел, и поступают запрашивающие запросы, имеющие вид — узнать что-то о подотрезке . Мы считаем, что запросы не модифицирующие, и известны

нам заранее, т.е. задача — оффлайновая.

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

сможем посчитать ответ на запрос или или или . Опишем теперь универсальную эвристику для всех таких задач. Отсортируем запросы по

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

Хорошим примером на данную эвристику является такая задача: узнать количество различных чисел в отрезке массива . Эта задача трудно поддаётся решению классическими методами.

Чуть более усложнённым вариантом этой задачи является задача с одного из раундов Codeforces.

Дерево Фенвика

Дерево Фенвика - это структура данных, дерево на массиве, обладающее следующими свойствами:

1)позволяет вычислять значение некоторой обратимой операции G на любом отрезке [L; R] за время O (log N);

2)позволяет изменять значение любого элемента за O (log N);

3)требует O (N) памяти, а точнее, ровно столько же, сколько и массив из N элементов;

4)легко обобщается на случай многомерных массивов.

Наиболее распространённое применение дерева Фенвика - для вычисления суммы на отрезке, т.е. функция G (X1, ..., Xk) = X1 + ... + Xk.

Дерево Фенвика было впервые описано в статье "A new data structure for cumulative frequency tables" (Peter M. Fenwick, 1994).

Описание

Для простоты описания мы предполагаем, что операция G, по которой мы строим дерево, - это сумма.

Пусть дан массив A[0..N-1]. Дерево Фенвика - массив T[0..N-1], в каждом элементе которого хранится сумма некоторых элементов массива A:

Ti = сумма Aj для всех F(i) <= j <= i,

где F(i) - некоторая функция, которую мы определим несколько позже.

Теперь мы уже можем написать псевдокод для функции вычисления суммы на отрезке [0; R] и для функции изменения ячейки:

int sum (int r)

{

int result = 0; while (r >= 0) {

result += t[r]; r = f(r) - 1;

}

return result;

}

void inc (int i, int delta)

{

для всех j, для которых F(j) <= i <= j

{

t[j] += delta;

}

}

Функция sum работает следующим образом. Вместо того чтобы идти по всем элементам массива A, она движется

по массиву T, делая "прыжки" через отрезки там, где это возможно. Сначала она прибавляет к ответу значение суммы на отрезке [F(R); R], затем берёт сумму на отрезке [F(F(R)-1); F(R)-1], и так далее, пока не дойдёт до нуля.

Функция inc движется в обратную сторону - в сторону увеличения индексов, обновляя значения суммы Tj только для тех позиций, для которых это нужно, т.е. для всех j, для которых F(j) <= i <= j.

Очевидно, что от выбора функции F будет зависеть скорость выполнения обеих операций. Сейчас мы рассмотрим функцию, которая позволит достичь логарифмической производительности в обоих случаях.

Определим значение F(X) следующим образом. Рассмотрим двоичную запись этого числа и посмотрим на его младший бит. Если он равен нулю, то F(X) = X. Иначе двоичное представление числа X оканчивается на группу

из одной или нескольких единиц. Заменим все единицы из этой группы на нули, и присвоим полученное число значению функции F(X).

Этому довольно сложному описанию соответствует очень простая формула:

F(X) = X & (X+1),

где & - это операция побитового логического "И".

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

Нам осталось только научиться быстро находить такие числа j, для которых F(j) <= i <= j.

Однако нетрудно убедиться в том, что все такие числа 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;

}

Система непересекающихся множеств

В данной статье рассматривается структура данных "система непересекающихся множеств" (на английском "disjoint-set-union", или просто "DSU").

Эта структура данных предоставляет следующие возможности. Изначально имеется несколько элементов, каждый из которых находится в отдельном (своём собственном) множестве. За одну операцию можно объединить два каких-либо множества, а также можно запросить, в каком множестве сейчас находится указанный элемент. Также, в классическом варианте, вводится ещё одна операция — создание нового элемента, который помещается в отдельное множество.

Таким образом, базовый интерфейс данной структуры данных состоит всего из трёх операций:

● — добавляет новый элемент , помещая его в новое множество, состоящее из одного него.

Построение эффективной структуры данных

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

Множества элементов мы будем хранить в виде деревьев: одно дерево соответствует одному множеству. Корень дерева — это представитель (лидер) множества.

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

Наивная реализация

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

Итак, вся информация о множествах элементов хранится у нас с помощью массива .

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

Наконец, реализация операции поиска лидера ( ) проста: мы поднимаемся по предкам от вершины ,

пока не дойдём до корня, т.е. пока ссылка на предка не ведёт в себя. Эту операцию удобнее реализовать рекурсивно (особенно это будет удобно позже, в связи с добавляемыми оптимизациями).

void make_set (int v) { parent[v] = v;

}

int find_set (int v) {

if (v == parent[v])

return v;

return find_set (parent[v]);

}

void union_sets (int a, int b) { a = find_set (a);

b = find_set (b); if (a != b)

parent[b] = a;

}

Впрочем, такая реализация системы непересекающихся множеств весьма неэффективна. Легко построить пример, когда после нескольких объединений множеств получится ситуация, что множество — это дерево, выродившееся в длинную цепочку. В результате каждый вызов будет работать на таком тесте за

время порядка глубины дерева, т.е. за .

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

Эвристика сжатия пути

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

Она заключается в том, что когда после вызова мы найдём искомого лидера множества, то запомним, что у вершины и всех пройденных по пути вершин — именно этот лидер . Проще всего это

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

int find_set (int v) {

if (v == parent[v]) return v;

return parent[v] = find_set (parent[v]);

}

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

Реализовать эту операцию можно и нерекурсивно, но тогда придётся осуществлять два прохода по дереву: первый найдёт искомого лидера, второй — проставит его всем вершинам пути. Впрочем, на практике нерекурсивная реализация не даёт существенного выигрыша.

Оценка асимптотики при применении эвристики сжатия пути

Покажем, что применение одной эвристики сжатия пути позволяет достичь логарифмическую асимптотику: на один запрос в среднем.

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

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

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

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

Зафиксируем теперь произвольную вершину и будем следить, как меняется ребро в её предка: сначала оно

отсутствует (пока вершина является лидером), затем проводится ребро из в какую-то вершину (когда множество

Рассмотрим этот путь и исключим из рассмотрения последнее ребро каждого класса (т.е. не более чем по одному ребру из класса ). Тем самым мы исключили рёбер из каждого запроса.

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

) означает логарифмическое время работы на один запрос в среднем.

Эвристика объединения по рангу

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

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

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

Приведём реализацию ранговой эвристики на основе размеров деревьев:

void make_set (int v) { parent[v] = v; size[v] = 1;

}

void union_sets (int a, int b) { a = find_set (a);

b = find_set (b); if (a != b) {

if (size[a] < size[b]) swap (a, b);

parent[b] = a; size[a] += size[b];

}

}

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

void make_set (int v) { parent[v] = v; rank[v] = 0;

}

void union_sets (int a, int b) { a = find_set (a);

b = find_set (b); if (a != b) {

if (rank[a] < rank[b]) swap (a, b);

parent[b] = a;

if (rank[a] == rank[b]) ++rank[a];

}

}