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

Определение:

Корневая эвристика (Sqrt-декомпозиция) — это метод, или структура данных, которая позволяет выполнять некоторые ассоциативные операции над отрезками (суммирование элементов подмассива, нахождение минимума/максимума и т.д.) за [math] O(\sqrt n)[/math].

Описание

Предпосчет

Пусть нам дан массив [math]A[/math] размерности [math]n[/math]. Cделаем следующий предпосчет:

• разделим массив [math]A[/math] на блоки длины [math]len = \lfloor \sqrt{n} \rfloor[/math] ;
• в каждом блоке заранее предпосчитаем необходимую нам операцию (сумму элементов, минимум/максимум и т.д.);
• результаты предпосчёта запишем в массив [math]B[/math] размерности [math]cnt[/math], где [math]cnt = \left\lceil \frac{n}{len} \right\rceil[/math] — количество блоков.

Пример предпосчета для запроса о подсчете суммы:

for(int i = 0; i < n; i++)
    B[i / len] += A[i]

Запрос

Пусть мы получили запрос на извлечение минимума на отрезке [math] [l \ldots r] [/math]. Отрезок может охватить некоторые блоки [math] b [/math] полностью, и не более двух блоков (начальный и конечный) — не полностью.

Проверка на то, что начальный блок вошел в отрезок не полностью, осуществляется как [math] l \mod len \neq 0 [/math]. Конечный блок проверяется как [math] (r + 1) \mod len \neq 0 [/math].

Для того чтобы найти минимум на отрезке [math][l \ldots r][/math], надо найти минимум среди элементов в "неполных блоках": [math][l \ldots (k+1)len-1][/math] и [math][(p+1)len \ldots r][/math], и минимума среди [math]b_i[/math] во всех блоках, начиная с k и заканчивая p: [math]\min_{i = l}^r a_i = \min(\min_{i = l}^{(k + 1)len - 1}(a_i),\min_{i = k}^p( b_i),\min_{i = p + 1}^r (a_i))[/math]

Изменение элемента

Теперь разрешим изменять элементы. Если меняется какой-то элемент [math]a_i[/math], то достаточно пересчитать значение [math]b_k[/math] в том блоке, в котором этот элемент находится:

[math]b_k\ = \min(new\_value, a_j)[/math], где [math]a_j[/math] - элементы блока [math]b_k[/math]

[math](k = i / len)[/math]

Оценка сложности

Размер каждого из "хвостов", очевидно, не превосходит длины блока [math]len[/math], а количество блоков не превосходит [math]cnt[/math]. Поскольку и [math]len[/math], и [math]cnt[/math] мы выбирали [math]\approx \sqrt{n}[/math], то всего для вычисления минимума и пересчитывания на отрезке [math][l \ldots r][/math] нам понадобится [math]O(\sqrt{n})[/math] операций.

Источники

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