Префиксные суммы
Один проход строит массив префиксных сумм — и любой диапазонный запрос закрывается одним вычитанием.
1function buildPrefixSum(arr: number[]): number[] {2 const p = [0]3 for (let i = 0; i < arr.length; i++) {4 p[i + 1] = p[i] + arr[i]5 }6 return p7}8 9// сумма на [l..r] = p[r + 1] - p[l]10function rangeSum(p: number[], l: number, r: number): number {11 return p[r + 1] - p[l]12}Проблема
Много запросов «чему равна сумма на [l..r]?». Пересчитывать каждый раз — O(n) на запрос. Префиксные суммы переносят работу в подготовку: O(n) один раз, O(1) на каждый запрос.
Что вы видите
Второй ряд p: p[i] — сумма первых i элементов. Запрос [l..r] — это p[r+1] − p[l]: подсвечиваются две ячейки префиксов, их разность и есть ответ.
Как это работает
Ключевая идея: сумма диапазона выражается через разность двух префиксов. Тот же приём в 2D (суммы подпрямоугольников), в разностных массивах (массовые прибавления на диапазоне) и в подсчёте балансов.
Пошаговый разбор
- 01
База
p[0] = 0 — пустой префикс.
- 02
Постройка
p[i+1] = p[i] + arr[i].
- 03
Запрос
Ответ = p[r+1] − p[l].
- 04
Сила
Любой диапазон — одно вычитание.
Complexity и ограничения
Работает и с отрицательными. Память O(n) на префиксы.
Edge cases
- Весь массив
p[n] − p[0].
- Пустой диапазон
p[l+1] − p[l+1] = 0.
- Частые обновления
Для точечных правок нужен Fenwick-дерево.
Где встречается в реальности
Аналитика
Суммы выручки за произвольные периоды из дневных totals.
Изображения
Интегральные изображения — 2D-префиксные суммы (HAAR-признаки).
Балансы
Сумма транзакций за период = разность снапшотов.
Связанные алгоритмы
«Любая сумма за O(1): один трюк с вычитанием»
Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.
Shorts 9:16
Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.