Корневая эвристика

Корневая эвристика

Корневая эвристика — обобщённое название методов и структур данных, опирающихся

Центральное равенство этой статьи: \(\sqrt x = \frac{x}{\sqrt x}\).

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

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

Дан массив \(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];
int 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;
}

Обновление пишется примерно так же:

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 {
            a[l] += x;
            l++;
        }
    }
 }

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

Корневая эвристика на запросах

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

int s[maxn]; // [0, r)
s[0] = 0

for (int i = 0; i < n; i++)
    s[i+1] = s[i] + a[i];

Подойдём теперь к задаче с другой стороны: разобьём на корневые блоки не массив, а запросы к нему. Будем обрабатывать каждый блок запросов независимо от других с помощью массива префикных сумм, который мы будем честно пересчитывать каждые \(\sqrt q\) запросов.

На каждый запрос суммы мы можем потратить \(O(1)\) времени на запрос к префиксным суммам, плюс \(\sqrt q\) времени на поправку на всех запросах из буфера.

struct query { int l, r, x; };
vector<query> buffer; // запросы, не учтенные в префиксных суммах

int sum(int l, int r) {
    int res = s[r+1] - s[l];
    for (query q : buffer)
        // пересечем запрос суммы со всеми запросами
        res += q.x * max(0, min(r, q.r) - max(l, q.l));
    return res;
}

void rebuild() {
    vector<int> d(n, 0);
    // массив дельт
    
    for (query q : buffer) {
        d[q.l] += x;
        d[q.r + 1] -= x;
    }
    buffer.clear();
    
    int delta = 0, running_sum = 0;
    for (int i = 1; i <= n; i++) {
        p[i] += running_sum;
        delta += d[i];
        running_sum += delta;
    }
}

void upd(int l, int r, int x) {
    buffer.push_back({l, r, x});
    if (buffer.size() == c)
        // буфер слишком большой; надо пересчитать префиксные суммы и очистить его
        rebuild();
}

Такое решение будет работать за \(O(n \sqrt q + q \sqrt q)\).

Превращение статических структур в динамические

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

Требуется добавлять точки в выпуклую оболочку и уметь находить касательные (то есть находить точку, которая максимизирует скалярное произведение \(a_i x + b_i y\)).

Мы можем так же каждые \(\sqrt q\) запросов перестраивать выпуклую оболочку, а при ответе на запрос касательной помимо кандидата из построенной выпуклой оболочки рассмотреть дополнительно \(\sqrt q\) скалярных произведений из точек из буфера.

Теперь чуть сложнее:

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

Разбьём запросы на блоки явно, и будем обрабатывать их по отдельности. На каждом блоке построим выпуклую оболочку только тех точек, которые существуют на всём её блоке, а остальные запросы сохраним в буфер. При ответе на запрос касательной помимо кандидата из построенной оболочки будем рассматривать все точки, которые существуют на момент данного запроса — найти все такие точки можно за \(\sqrt q\), проанализировав историю текущего блока.

Часто, если удалений в задаче нет или их можно как-то эмулировать, можно применить похожую, но более мощную технику: поддерживать \(O(\log n)\) структур (например, выпуклых оболочек) размеров степени двойки, причём так, что нет двух структур одинакового размера. При добавлении новой точки мы создаем для неё новую структуру размера 1. Дальше, если структура размера 1 уже существует, то мы объединяем эти две структуры и создаём структуру размера 2. Если структура размера 2 уже существовала, то мы объединяем её и создаём структуру размера 4, и так далее. Запрос мы будем передавать во все \(O(\log n)\) базовых структур и объединять ответы.

«Алгоритм Мо»

Теперь обсудим еще одно решение этой же задачи. На этот раз мы будем группировать запросы и по временным, и по пространственным признакам.

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

vector< pair<int, int> > b[c];
s_dec[l / c].a.push_back({l, r});

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

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

struct query { int l, r, idx; };
// idx -- это номер запроса, на который нужно ответить
struct block {
    vector<q> a;
};

for(int i = 0; i < q; i++) {
    s_dec[l / s].a.push_back({l, r, i});
}

for(int i = 0; i < s; i++) {
    sort(all(s_dec[i].a), comp);
}

for(int i = 0; i < s; i++) {
    int l = i * s, r = i * s;
    int ans = 0;
    for(int j = 0; j < s_dec[i].a.size(); j++) {
        int tl = s_dec[i].a[j].l, tr = s_dec[i].a[j].r;
        while (r > tr){
            r—;
            ans -= a[r];
        }
        while(r < tr) {
            ans += a[r];
            r++;
        }
        while(l > tl) {
            l--;
            ans += a[l];
        }
        while(l < tl) {
            ans -= a[l];
            l++;
        }
        answ[s_dec[i].a[j].index] = ans;
}

Подумаем над асимптотикой данного алгоритма, для каждого запроса левая граница пройдет не более, чем длину блока, но при этом правая граница идет только вперед, а следовательно для одного блока пройдет не более, чем длину массива, то есть суммарно алгоритм работает за \(O(N*\sqrt(M) + M*\sqrt(N))\).

Но зачем для такой легкой задачи использовать такой сложный алгоритм? Алгоритм Мо может помочь нам в ответе на гораздо более сложные вопросы - k-ая статистика на отрезке, медиана отрезка, наиболее встречающийся элемент на отрезке и так далее.

Деление на тяжелые и легкие объекты

В математике очень часто встречается идея рассмотреть все объекты с каким-то свойством < \(\sqrt{N}\) и больше.

Например всем известный алгоритм проверки на простоту чисел(рассмотрим делители < \(\sqrt{N}\) и больше, но так как для любого делителя больше корня можно найти делитель меньше корня => нам надо честно рассмотреть только первые) или например факт, что если суммарная длина строк = \(N\), то различных длин строк будет не более \(\sqrt{N}\) или если вы увидели ограничение \(A * B <= N\), то одно из чисел < \(\sqrt{N}\).

Подбор константы

В корневой декомпозиции очень важен размер блока. Обычно брать s = \(\sqrt{N}\) или близкое к ней число(желательно, чтобы делилось на максимально возможную степень двойки) оптимально, но сейчас мы поговорим об особых случаях. Пусть s - размер блока и мы знаем, что алгоритм работает за \(O(N * s + \frac{N ^ 2 * \log(N)}{ s})\), тогда если взять s = \(\sqrt{N} * 4\), то алгоритм будет работать быстрее, чем при s = \(\sqrt{N}\), то есть при определении размера блока первым делом надо смотреть на асимптотику.

Корзины

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