Префиксные суммы и разности

Один проход предобработки — и сумма любого отрезка считается за O(1). Плюс обратный приём: массив разностей.

Префиксная сумма — массив, где элемент pref[i] хранит сумму первых i чисел, что позволяет узнать сумму любого отрезка за одно вычитание.

Зачем это нужно

Очень частый сценарий: дан массив и много запросов вида «какова сумма на отрезке от l до r?». Считать каждую сумму циклом — это O(n) на запрос, и при q запросах получаем O(n·q), что при n,q = 10^5 равно 10^10 — TLE. Префиксные суммы решают это блестяще: после линейной предобработки каждый запрос — O(1). Это один из самых дешёвых и часто используемых приёмов; он же лежит в основе многих формул в ДП и комбинаторике.

Идея «на пальцах»

Заведём массив pref на единицу длиннее исходного, где pref[i] = сумма первых i элементов (pref[0] = 0). Тогда сумма элементов с индекса l по r включительно — это pref[r+1] − pref[l]. Геометрически: из «суммы до правого конца» вычитаем «сумму до левого края» — остаётся ровно нужный кусок. Как с пробегом на одометре: путь между двумя точками — разность показаний.

a = [3, 1, 4, 1, 5, 9, 2, 6]
n = len(a)

# Предобработка за O(n): pref[i] = a[0] + ... + a[i-1]
pref = [0] * (n + 1)
for i in range(n):
    pref[i + 1] = pref[i] + a[i]

def rng(l, r):                 # сумма a[l..r] включительно за O(1)
    return pref[r + 1] - pref[l]

print("Сумма a[2..5] =", rng(2, 5))   # 4+1+5+9
print("Сумма a[0..7] =", rng(0, 7))   # вся сумма

Главное — сдвиг на единицу: pref[i+1] = pref[i] + a[i], а запрос — pref[r+1] - pref[l]. Лишний нулевой элемент pref[0] избавляет от особого случая l = 0.

Вывод:

Сумма a[2..5] = 19
Сумма a[0..7] = 31

Двумерные префиксные суммы

Тот же приём расширяется на матрицы: pref[i][j] — сумма прямоугольника от (0,0) до (i−1,j−1). Сумма произвольного прямоугольника считается по формуле включения-исключения за O(1). Это решает задачи вида «сумма в подматрице» и встречается в задачах на сетках. Формула: S = pref[r2][c2] − pref[r1][c2] − pref[r2][c1] + pref[r1][c1].

Обратный приём: массив разностей

А если наоборот — нужно много раз прибавить число на отрезке, а ответ узнать в конце? Тут помогает «зеркальный» приём — массив разностей. Чтобы прибавить x на отрезке [l, r], делаем всего две операции: diff[l] += x и diff[r+1] -= x. После всех обновлений берём префиксные суммы от diff — и получаем итоговый массив.

n = 6
diff = [0] * (n + 1)
# каждый апдейт (l, r, +x) — за O(1), без прохода по отрезку:
updates = [(1, 3, 5), (2, 5, 2), (0, 1, 10)]
for l, r, x in updates:
    diff[l] += x
    diff[r + 1] -= x

# восстановление массива: префиксная сумма diff
a = [0] * n
run = 0
for i in range(n):
    run += diff[i]
    a[i] = run
print("Массив после диапазонных прибавлений:", a)

Почему работает: запись +x в позицию l «включает» прибавку начиная с l, а −x в r+1 «выключает» её после r. Когда мы берём префиксную сумму, прибавка x накапливается ровно на отрезке [l, r]. Каждый из m апдейтов — O(1), восстановление — O(n): итого O(n + m) вместо O(n·m).

Вывод:

Массив после диапазонных прибавлений: [10, 15, 7, 7, 2, 2]

Сравнение приёмов

Важно: префиксные суммы и массив разностей хороши, когда обновления и запросы не перемешаны. Если они идут вперемешку (обновили — спросили — снова обновили), нужна более мощная структура — дерево отрезков или дерево Фенвика, к которым мы придём дальше.

Подводные камни

• Off-by-one. Чаще всего ошибаются в индексах: запомни сумма[l..r] = pref[r+1] - pref[l] и держи pref длиннее на 1.
• Размер diff. Массив разностей должен иметь длину n+1, чтобы diff[r+1] при r = n−1 не вышел за границы.
• Переполнение? В Python int неограничен, так что суммы не переполнятся — приятный бонус по сравнению с C++.

Итог

• Префиксные суммы: предобработка O(n), затем сумма любого отрезка за O(1) через pref[r+1] − pref[l].
• Массив разностей: диапазонное прибавление за O(1), итоговый массив — префиксной суммой.
• Оба приёма — для «пакетных» сценариев без перемешивания запросов и обновлений.
• Когда обновления и запросы идут вперемешку — нужно дерево отрезков.