Статистики на отрезках. Корневая эвристика
Содержание
Определение
Корневая эвристика (Sqrt-декомпозиция) — это метод, или структура данных, которая позволяет выполнять некоторые типичные операции (суммирование элементов подмассива, нахождение минимума/максимума и т.д.) за
.Описание
Привидем описание для операции суммирования
Дан массив
. Cделаем следующий предпосчёт: разделим массив A на блоки длины (округлённому к целому), и в каждом блоке заранее предпосчитаем нужную операцию в нём. Пусть len — это длина блока , а — количество блоков:Через
мы обозначили результат предпосчёта в k-ом подотрезке.Для того чтобы посчитать сумму в отрезке
, надо просуммировать элементы только в двух "хвостах": и , и просуммировать значения во всех блоках, начиная с k и заканчивая p:Оценка сложности
Размер каждого из "хвостов", очевидно, не превосходит длины блока
, а количество блоков не превосходит . Поскольку и , и мы выбирали , то всего для вычисления суммы в отрезке нам понадобится операций.