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

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

Корневая эвристика (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 i = 0 to n
    B[i / len] += A[i]

Обработка запроса

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

Таким образом, для того чтобы найти, например, сумму на отрезке [math][l, r][/math] нам необходимо вручную посчитать сумму на "хвостах" и сложить с суммой полных блоков, предпосчет которых мы сделали заранее.

Пример реализации обработки запроса "подсчет суммы на отрезке [math][l, r][/math] " :

left = l / len
right = r / len
end = (left + 1) * len - 1
sum = 0

if left == right
    for i = l to r
	sum += A[i]
else
    for i = l to end
        sum += A[i]
    for i = left + 1 to right - 1
        sum += B[i]
    for i = right * len to r
        sum += A[i]

Запрос на изменение элемента

Для реализации данного запроса нам необходимо поменять всего два элемента, т.к. каждый элемент входит в ровно один блок массива [math]B[/math].

Пример реализации:

[math]p[/math] - номер элемента из массива [math]A[/math], который необходимо заменить; [math]delta[/math] - на сколько нужно изменить данный элемент.

A[p] += delta
B[p / len] += delta

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

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

Источники

• Maximal:: algo:: Sqrt - декомпозиция
• Sqrt-декомпозиция (корневая оптимизация)