Что такое префиксные суммы и какие задачи они решают?

Префиксная сумма `pre[i]` — сумма первых `i` элементов; после предподсчёта за `O(n)` сумма любого отрезка `[l, r]` считается за `O(1)` как `pre[r + 1] − pre[l]`.

Базовые приёмы

• Массив длины n + 1 с pre[0] = 0 избавляет от проверок на границе.
• 2D-версия: сумма прямоугольника через включения-исключения из четырёх значений pre.
• Та же идея работает для XOR, количества элементов с признаком, чётности.
• Разностный массив — обратная операция: прибавить x на отрезке за O(1) (d[l] += x, d[r + 1] −= x), а итог восстановить одной префиксной суммой.

Подмассивы с суммой k

Сумма a[l..r] = k ⇔ pre[r + 1] − pre[l] = k. Храним в словаре, сколько раз встречался каждый префикс:

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

O(n) и, в отличие от скользящего окна, корректно работает с отрицательными числами.

Ограничения

• Массив должен быть статичным: одно изменение элемента требует пересчёта O(n).
• В языках с фиксированной разрядностью префиксы быстро переполняют int32 — берут 64-битный тип.

Коротко для собеседования

Префиксные суммы предподсчитываются один раз за O(n), после чего сумма любого отрезка — разность двух чисел. В связке с Map они считают подмассивы с суммой k даже при отрицательных числах; если массив меняется между запросами, нужен Фенвик или дерево отрезков.