Корневые оптимизации можно использовать много для чего, в частности в контексте структур данных.
#Корневая декомпозиция на массивах
Сделаем вид, что про дерево отрезков мы не знаем, и рассмотрим следующую задачу.
Задача. Дан массив $a$ длины $n$. Требуется отвечать на $q$ запросов одного из двух типов:
- Найти сумму на отрезке $[l, r]$.
- Увеличить все элементы на отрезке [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)$ операций на запрос:
- Для всех блоков, лежащих целиком внутри запроса, просто возьмём уже посчитанные суммы и сложим.
- Для блоков, пересекающихся с запросом только частично (их максимум два — правый и левый), проитерируемся по нужным элементам и поштучно прибавим к ответу.
Есть много разных стилей, как это реализовать, но автор предпочитает такой:
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$ запросов одного из трёх видов:
- Вставить элемент $x$ на позицию $k$ (слева от него окажется ровно $k$ элементов).
- Удалить элемент с позиции $k$.
- Найти минимум на интервале $[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)$ элементов по отдельности, но с течением времени может получиться, что либо блоков слишком много, либо есть слишком большие блоки. Есть два способа решать эту проблему:
- После каждой операции добавления или удаления смотреть на затронутый блок, и если его размер больше $2 \cdot \sqrt n$, то разделять его на два, а также если он и его сосед в сумме дают меньше $n$, то смерджить их в один.
- Завести глобальный счетчик операций и просто перестраивать целую структуру каждые $\sqrt q$ запросов (выписать обратно в массив и заново разделить на равные блоки).
В первом случае мы потенциально тратим $O(\sqrt n)$ операций на сплиты и мерджи, но гарантируем инварианты, а во втором получаем ровно $\sqrt n$ помножить на стоимость построения.
Второй вариант проще кодить (ведь структуру в любом случае нужно изначально строить). Примечательно, что бывают ситуации, когда перестраивать структуру не так выгодно, как поддерживать в сбалансированном состоянии — когда мердж дешевле перестроения с нуля.
Более реальный пример задачи: IOI 2011 «Dancing Elephants».