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

Определение

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

Описание

Привидем описание для операции суммирования

Дан массив [math]A[0 \ldots n-1][/math]. Cделаем следующий предпосчёт: разделим массив A на блоки длины [math]\sqrt{n}[/math] (округлённому к целому), и в каждом блоке заранее предпосчитаем нужную операцию в нём. Пусть len — это длина блока [math](len \approx \sqrt{n})[/math], а [math]cnt = \left\lceil \frac{n}{len} \right\rceil[/math] — количество блоков:

Через [math]b_k[/math] мы обозначили результат предпосчёта в k-ом подотрезке.

Для того чтобы посчитать сумму в отрезке [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]\sum_{i = l}^r a_i = \sum_{i = l}^{(k + 1)len - 1} + a_i \sum_{i = k}^p b_i + \sum_{i = p + 1}^r a_i[/math]

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

[math]b_k\ += a_i - old\_a_i\_val[/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 - декомпозиция