sqrt-structures.md

title	Корневые структуры
authors	Сергей Слотин Иван Сафонов
weight	6
date	2022-08-16 00:00:00 UTC

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

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

Сделаем вид, что про дерево отрезков мы не знаем, и рассмотрим следующую задачу.

Задача. Дан массив $a$ длины $n$. Требуется отвечать на $q$ запросов одного из двух типов:

1. Найти сумму на отрезке $[l, r]$.
2. Увеличить все элементы на отрезке [l, r] на $x$.

Разделим весь массив на блоки по $c \approx \sqrt{n}$ элементов и посчитаем сумму на каждом блоке. Так как блоки не пересекаются, суммарно это будет работать за $O(n)$.

// c это и количество блоков, и также их размер; оно должно быть чуть больше корня
const int maxn = 1e5, c = 330;
int a[maxn], b[c], add[c];

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

Заведем также массив add размера $\sqrt n$, который будем использовать для отложенной операции прибавления на блоке: будем считать, что реальное значение $i$-го элемента равно a[i] + add[i / c].

Теперь мы можем отвечать на запросы первого типа за $O(\sqrt n)$ операций на запрос:

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

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

int sum(int l, int r) {
    int res = 0;
    while (l <= r) {
        // если мы находимся в начале блока и он целиком в запросе
        if (l % c == 0 && l + c - 1 <= r) {
            res += b[l / c];
            l += c; // мы можем прыгнуть сразу на блок
        }
        else {
            res += a[l] + add[l / c];
            l += 1;
        }
    }
    return res;
}

Обновление пишется примерно так же — для целиком лежащих кусков обновляем add и сумму, для остальных отдельные элементы:

void upd(int l, int r, int x) {
    while (l <= r) {
        if (l % c == 0 && l + c - 1 <= r) {
            b[l / c] += c * x;
            add[l / c] += x;
            l += c;
        }
        else {
            b[l / c] += x;
            a[l] += x;
            l++;
        }
    }
 }

Обе операции будут работать за $O(\sqrt n)$, потому что нужных «центральных» блоков всегда не более $\sqrt n$, а в граничных блоках суммарно не более $2 \sqrt n$ элементов.

Внутренние структуры

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

Например, хеш-таблица внутри каждого блока позволяет отвечать на запросы вида «число элементов равных $x$ на отрезке», а отсортированным массивом можно решать задачи вида «количество чисел меньших $x$ на отрезке» или «сумма на прямоугольнике».

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

Для этого нужно смотреть даже не на асимптотику «блочной» и «поштучной» частей, а скорее на относительное реальное время их работы — учитывая, что походы в какое-нибудь декартово дерево совсем не в логарифм раз медленнее линейного, хорошо векторизуемого прохода по массиву. По этой же причине очень часто в корневых эвристиках корень «меньше» логарифма.

Подвижные элементы

Задача. Дан массив $a$ длины $n$. Требуется отвечать на $q$ запросов одного из трёх видов:

1. Вставить элемент $x$ на позицию $k$ (слева от него окажется ровно $k$ элементов).
2. Удалить элемент с позиции $k$.
3. Найти минимум на интервале $[l, r]$.

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

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

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

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

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

vector< vector<int> > blocks;

// возвращает индекс блока и индекс элемента внутри блока
pair<int, int> find_block(int pos) {
    int idx = 0;
    while (blocks[idx].size() <= pos)
        pos -= blocks[idx++].size();
    return {idx, pos};
}

Решение в таком виде будет хорошо работать только первое время, когда каждая операция будет просматривать не более $O(\sqrt n)$ блоков и не более $O(\sqrt n)$ элементов по отдельности, но с течением времени может получиться, что либо блоков слишком много, либо есть слишком большие блоки. Есть два способа решать эту проблему:

1. split-merge: После каждой операции добавления или удаления смотреть на затронутый блок, и если его размер больше $2 \cdot \sqrt n$, то разделять его на два, а также если он и его сосед в сумме дают меньше $\sqrt n$, то объединить их в один.
2. split-rebuild: Завести глобальный счетчик операций и просто перестраивать целую структуру каждые $\sqrt q$ запросов (выписать обратно в массив и заново разделить на равные блоки).

В первом случае мы потенциально тратим $O(\sqrt n)$ операций на сплиты и мерджи, но гарантируем инварианты, а во втором получаем ровно $\sqrt n$ помножить на стоимость построения.

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

Более реальный пример задачи: IOI 2011 «Dancing Elephants».