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

Признак в условии

• «сумма подмассива», «сколько подмассивов с суммой X»
• много запросов «сумма на отрезке» к неизменному массиву
• есть отрицательные числа, из-за которых окно не годится

Идея

pre[i] - сумма первых i элементов. Тогда сумма отрезка [l, r] равна pre[r+1] − pre[l] за O(1). Для подсчёта подмассивов с нужной суммой храним частоты префиксных сумм в Map.

Шаблон

const seen = new Map([[0, 1]]);   // пустой префикс встречался один раз
let sum = 0, count = 0;
for (const n of nums) {
  sum += n;
  count += seen.get(sum - k) || 0;
  seen.set(sum, (seen.get(sum) || 0) + 1);
}

Сложность

Время O(n), память O(n).

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

• забыт начальный ноль в Map - теряются подмассивы, начинающиеся с первого элемента
• попытка решить окном при наличии отрицательных чисел
• off-by-one в границах: сумма [l, r] это pre[r+1] − pre[l], а не pre[r] − pre[l]

Мнемоника

«Разность префиксов - это отрезок»

Не путать с

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

Задачи на этот паттерн

• префиксные суммы
• число подмассивов с суммой k
• точка равновесия
• произведение всех, кроме себя
• подмассивы, делящиеся на K

Суть

Префиксный массив хранит суммы первых k элементов. Тогда сумма любого отрезка это разность двух префиксов: O(1) вместо прохода.

const pre = [0];
for (const x of arr) pre.push(pre.at(-1) + x);
// сумма arr[i..j] включительно:
const sum = pre[j + 1] - pre[i];

pre на единицу длиннее массива, pre[0] = 0. Такой сдвиг убирает особые случаи для отрезков с начала.

Как распознать по условию

• много запросов «сумма на отрезке», массив не меняется;
• «количество подмассивов с суммой k», «сумма делится на k»;
• в массиве есть отрицательные числа, поэтому окно не работает;
• произведение всех кроме себя (префиксные и суффиксные произведения);
• массовые прибавления на отрезках.

Шаблон: префикс + Map

function countSubarrays(nums, k) {
  const seen = new Map([[0, 1]]); // пустой префикс
  let cur = 0, count = 0;
  for (const x of nums) {
    cur += x;
    count += seen.get(cur - k) ?? 0;
    seen.set(cur, (seen.get(cur) ?? 0) + 1);
  }
  return count;
}

Логика: подмассив (i, j] даёт k, если pre[i] = pre[j] - k. Сколько таких i встречалось раньше, столько и подмассивов заканчивается в j.

Вариации:

• самый длинный подмассив с суммой k: в Map храним первый индекс префикса;
• сумма делится на k: ключ это остаток ((cur % k) + k) % k (в JS % от отрицательного отрицателен).

Массив разностей

Обратная операция. Прибавить v на [l, r]: d[l] += v; d[r + 1] -= v. После всех запросов префиксная сумма по d даёт итоговые прибавки. O(1) на запрос.

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

P[r+1][c+1] = a[r][c] + P[r][c+1] + P[r+1][c] - P[r][c]. Сумма прямоугольника считается включением-исключением за O(1).

Сложность

Построение O(n), запрос O(1), память O(n). Префикс + Map: O(n) времени и памяти.

Ловушки

• Сдвиг индексов: pre[j + 1] - pre[i], а не pre[j] - pre[i].
• Забыть seen.set(0, 1).
• Обновлять Map до подсчёта ответа: при k = 0 элемент посчитает сам себя как пустой подмассив.
• Отрицательный остаток % в JS.

Что спросят на собесе

• Как отвечать на запросы суммы на отрезке за O(1)?
• Посчитай подмассивы с суммой k, если есть отрицательные числа.
• Почему тут не подходит скользящее окно?
• Как получить произведение всех элементов кроме текущего без деления?