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

Есть массив и запросы к его отрезкам. Отвечать перебором - $O(n)$ на запрос. Предпосчитать ответы на все отрезки - $O(n^2)$ памяти. Нужен способ посередине.

Идея

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

Тогда любой отрезок $[l, r]$ распадается на три части:

• левый огрызок - хвост блока, в котором лежит $l$;
• середина - целые блоки между ними;
• правый огрызок - начало блока, в котором лежит $r$.

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

graph LR
  A["огрызок: до 2B элементов"] --- B["целые блоки: до n/B штук"] --- C["огрызок"]

int query(int l, int r) {                       // нумерация с нуля
    int bl = l / B, br = r / B, answer = NEUTRAL;
    if (bl == br) {
        for (int i = l; i <= r; i++) answer = combine(answer, a[i]);
        return answer;
    }
    for (int i = l; i < (bl + 1) * B; i++) answer = combine(answer, a[i]);
    for (int b = bl + 1; b < br; b++)          answer = combine(answer, block[b]);
    for (int i = br * B; i <= r; i++)          answer = combine(answer, a[i]);
    return answer;
}

Случай «оба конца в одном блоке» надо выписать отдельно: иначе левый огрызок вылезет за $r$.

Почему корень

Запрос стоит $O(B)$ на огрызки плюс $O(n/B)$ на середину. Сумма $B + n/B$ минимальна при $B = \sqrt{n}$ и равна $2\sqrt{n}$.

Это и есть всё обоснование - обычное неравенство о среднем. Никакой магии в корне нет: он просто уравнивает две части работы.

Насколько важно попасть в корень

Измерено на массиве из $10^5$ чисел и 30 000 запросов максимума, по 20 прогонов:

размер блока	время
8	1335 мс
32	343 мс
100	135 мс
200	112 мс
316 (это $\sqrt{n}$)	129 мс
500	174 мс
1000	321 мс
10000	2967 мс

Три наблюдения, каждое практическое.

Минимум не ровно в корне. Он оказался при $B = 200$, а не при 316. Причина простая: проход по огрызку и проход по блокам стоят по-разному - у первого лучше локальность, зато второй короче. Формула $B + n/B$ считает их одинаковыми, а процессор - нет.

Дно широкое. Всё от 100 до 500 укладывается в полтора раза от лучшего. Подбирать точное значение бессмысленно.

Края дорогие. Ошибиться в тридцать раз - значит замедлиться в двадцать. Так что корень брать надо, а вот шлифовать его - нет.

Когда корневая - правильный выбор

Она проигрывает дереву отрезков по асимптотике: $\sqrt{n}$ против $\log n$. Зато выигрывает в другом.

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

Отсюда правило: если задача укладывается в дерево отрезков - берите его. Если операция странная, а $n$ до $10^5$ - берите корневую и не мучайтесь.