Префиксные суммы

Как построить префиксные суммы

Введение

Префиксные суммы — один из самых фундаментальных приёмов в спортивном программировании. Они помогают эффективно отвечать на запросы по отрезкам, заранее вычислять полезную информацию и превращать многие идеи перебора в быстрые решения.

Основная идея проста: вместо того чтобы пересчитывать суммы для каждого запроса, мы один раз строим накопленные значения и переиспользуем их всякий раз, когда нужно.

Идея

Предположим, у нас есть массив $a$ длины $n$. Мы строим вспомогательный массив pref, где pref[i] хранит сумму первых i элементов.

Рекуррентная формула:

• $pref_i = pref_{i-1} + a_i$