Ctrl K
ВойтиНачать бесплатно
Урок

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

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

Представь выписку по банковской карте, где после каждой операции указан остаток на счёте. Сколько ты потратил с 3-го по 10-е число? Не нужно складывать все чеки — достаточно взять остаток на 10-е, вычесть остаток на 2-е, и ответ готов за одно действие.

Префиксные суммы работают так же. Один раз заранее считаем «накопленный остаток» для каждой позиции массива. После этого сумма любого отрезка считается за O(1) — одним вычитанием.

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

Возьмём массив:

30
11
42
13
54
95
26
исходный массив nums

Построим prefix, где prefix[i] — сумма первых i элементов. Длина у него на 1 больше, и он начинается с нуля:

00
31
42
83
94
145
236
257
prefix: prefix[0] = 0 — сумма пустого начала

Правило построения: prefix[i+1] = prefix[i] + nums[i]. Каждое число равно предыдущему плюс очередной элемент.

💡 Ведущий ноль — главный трюк. С ним формула одинаковая для любого отрезка, и не нужен отдельный if для случая «отрезок с самого начала».

Сумма отрезка одним вычитанием

Нужна сумма nums[2..4], то есть 4 + 1 + 5 = 10:

30
11
l ↓ 42
13
r ↓ 54
95
26
отрезок nums[2..4]
00
31
l ↓ 42
83
94
r+1 ↓ 145
236
257
prefix[5] − prefix[2] = 14 − 4 = 10

Формула: sum(l..r) = prefix[r+1] - prefix[l]. В prefix[r+1] лежит всё до r включительно. Вычитаем всё, что было до l, и остаётся ровно наш отрезок.

Шаблон кода

def build_prefix(nums):
    prefix = [0] * (len(nums) + 1)
    for i, x in enumerate(nums):
        prefix[i + 1] = prefix[i] + x  # накопленная сумма
    return prefix

def range_sum(prefix, l, r):
    # сумма nums[l..r] включительно
    return prefix[r + 1] - prefix[l]

p = build_prefix([3, 1, 4, 1, 5, 9, 2])
print(range_sum(p, 2, 4))  # 10

Сложность

Операция Время Память
Построение prefix O(n) O(n)
Один запрос суммы O(1) —
q запросов O(n + q) O(n)

Без префиксов каждый запрос стоил бы O(n), а все вместе — O(n·q). Разница огромная.

Префиксы + хеш-таблица: подсчёт подмассивов

Частый вопрос на собесе: «сколько подмассивов имеют сумму ровно k?». Перебирать все пары (l, r) слишком долго, это O(n²). Перепишем условие через префиксы:

prefix[r+1] - prefix[l] = k ⟺ prefix[l] = prefix[r+1] - k

Получается, что для каждой правой границы нужно узнать, сколько раз раньше встречалась префиксная сумма, равная текущий_префикс − k. Такой вопрос «сколько раз я уже видел это значение?» хеш-таблица решает за O(1).

Схема рассуждения:

  • идём по массиву слева направо и держим текущую накопленную сумму;
  • в хеш-таблице храним «префиксная сумма → сколько раз встречалась»;
  • на каждом шаге сначала смотрим в таблицу, потом записываем туда текущий префикс.

Получается один проход: O(n) по времени и O(n) по памяти. Собрать это в код — твоё упражнение в практике главы. Подсказка: подумай, что положить в таблицу до первого шага, чтобы учесть подмассивы, начинающиеся с индекса 0. Вспомни наш ведущий ноль.

Когда префиксы лучше скользящего окна

Окно опирается на монотонность: расширил окно, и сумма выросла; сузил, и она уменьшилась. Это верно только для неотрицательных чисел.

20
-11
22
13
-34
45
отрицательные числа ломают логику окна

Здесь при добавлении -3 сумма падает. Окно не понимает, двигать левую границу или правую, и может пропустить ответ. Префиксам знаки безразличны: формула prefix[r+1] - prefix[l] верна всегда.

Ситуация Что брать
Только неотрицательные числа, «самый короткий/длинный отрезок с суммой ≥ k» Скользящее окно, O(1) памяти
Есть отрицательные числа Префиксы (+ хеш-таблица)
Много запросов суммы на неизменном массиве Префиксы
Подсчёт количества отрезков с точной суммой Префиксы + хеш-таблица

Как это звучит на собесе

«Посчитаю массив префиксных сумм с ведущим нулём за O(n). Тогда сумма отрезка [l, r] равна prefix[r+1] − prefix[l] и считается за O(1). В массиве есть отрицательные числа, поэтому окно не подходит: нет монотонности. Условие на сумму отрезка я переформулирую как поиск нужного префикса в хеш-таблице».

Интервьюеру важно услышать, что ты сам заметил проблему с отрицательными числами.

Частые ошибки

  • Сдвиг на единицу. Путают prefix[r] и prefix[r+1]. Проверь формулу на отрезке из одного элемента: prefix[i+1] − prefix[i] должно дать nums[i].
  • Забыли ведущий ноль. Отрезки, начинающиеся с индекса 0, считаются неправильно.
  • Переполнение. В Java, C++ и Go сумма многих int легко выходит за предел типа, поэтому храни префиксы в long/long long/int64.
  • Окно на отрицательных числах. Код выглядит правильно и проходит простые тесты, но на хитрых падает.
  • Порядок работы с хеш-таблицей. Если записать текущий префикс до проверки, можно посчитать пустой подмассив или дважды учесть один и тот же.

Теперь у тебя есть инструмент, который превращает вопрос «сумма отрезка» в одно вычитание. Дальше закрепим его на задачах.