Подготовка к алгоритмическим задачам
Префиксные суммы: мгновенные запросы суммы на отрезке
Задача, с которой всё начинается
Дан массив чисел и много запросов вида «какая сумма элементов с индекса l по индекс r?». Запросов может быть 10⁵, массив тоже на 10⁵ элементов.
В лоб каждый запрос — это цикл от l до r, то есть O(n) на запрос и O(n·q) суммарно. Десять миллиардов операций. Не вариант.
Префиксные суммы позволяют отвечать на такой запрос за O(1) после одной подготовки за O(n). Это одна из тех техник, которые выглядят до смешного просто, но закрывают целый класс задач.
Как это работает
Строим вспомогательный массив prefix, где prefix[i] — сумма первых i элементов исходного массива.
const nums = [3, 1, 4, 1, 5, 9]; // prefix[0] = 0 (пустой префикс) // prefix[1] = 3 (3) // prefix[2] = 4 (3+1) // prefix[3] = 8 (3+1+4) // prefix[4] = 9 (3+1+4+1) // prefix[5] = 14 (3+1+4+1+5) // prefix[6] = 23 (3+1+4+1+5+9)
Теперь сумма на отрезке [l, r] включительно — это просто разность:
sum(l, r) = prefix[r + 1] - prefix[l]
Смысл разности такой: из суммы всего, что идёт до r включительно, вычитаем сумму всего, что идёт до l. Остаётся ровно нужный кусок.
function buildPrefix(nums) { const prefix = new Array(nums.length + 1).fill(0); for (let i = 0; i < nums.length; i++) { prefix[i + 1] = prefix[i] + nums[i]; } return prefix; } function rangeSum(prefix, l, r) { return prefix[r + 1] - prefix[l]; } const prefix = buildPrefix([3, 1, 4, 1, 5, 9]); rangeSum(prefix, 1, 3); // 6 → 1 + 4 + 1 rangeSum(prefix, 0, 5); // 23 → вся сумма
Тот же код на Python:
from itertools import accumulate nums = [3, 1, 4, 1, 5, 9] prefix = [0] + list(accumulate(nums)) def range_sum(l: int, r: int) -> int: return prefix[r + 1] - prefix[l] range_sum(1, 3) # 6
Почему массив на единицу длиннее
Обратите внимание на лишний нулевой элемент в начале. Без него пришлось бы отдельно обрабатывать случай l == 0, потому что prefix[l - 1] вылезет за границу. Фиктивный ноль убирает это ветвление и делает формулу единообразной. Это стандартный приём, и на собеседовании он читается как признак опыта.
Уровень выше: подмассивы с заданной суммой
Здесь префиксные суммы раскрываются по-настоящему. Задача: сколько существует непрерывных подмассивов с суммой ровно k?
Наивно — перебрать все пары границ, O(n²). Но заметим: сумма на отрезке (j, i] равна k тогда и только тогда, когда
prefix[i] - prefix[j] = k ⟺ prefix[j] = prefix[i] - k
То есть, стоя в точке i, нам нужно узнать, сколько раз раньше встречалось значение prefix[i] - k. А это работа для хеш-таблицы.
function subarraySum(nums, k) { // сколько раз встречалась каждая префиксная сумма const seen = new Map([[0, 1]]); // пустой префикс встретился один раз let running = 0; let count = 0; for (const num of nums) { running += num; // сколько префиксов дают нужную разность count += seen.get(running - k) || 0; seen.set(running, (seen.get(running) || 0) + 1); } return count; } subarraySum([1, 1, 1], 2); // 2 subarraySum([1, 2, 3], 3); // 2 → [1,2] и [3] subarraySum([1, -1, 0], 0); // 3
Сложность — O(n) по времени и памяти.
Два места, где здесь ошибаются:
Забывают инициализировать seen парой {0: 1}. Без неё потеряются подмассивы, начинающиеся с нулевого индекса. Тест [3], k=3 сразу это вскроет.
Сначала обновляют seen, потом считают count. При k = 0 это приведёт к тому, что элемент засчитает сам себя. Порядок важен: сначала ищем, потом записываем.
Отдельно стоит подчеркнуть: в отличие от скользящего окна, этот подход работает с отрицательными числами. Именно поэтому его и спрашивают — окно здесь неприменимо, и интервьюер проверяет, понимаете ли вы разницу.
Двумерный случай
Для матриц идея та же, только префикс двумерный: prefix[i][j] — сумма прямоугольника от левого верхнего угла до (i-1, j-1).
function build2D(matrix) { const rows = matrix.length; const cols = matrix[0].length; const prefix = Array.from({ length: rows + 1 }, () => new Array(cols + 1).fill(0) ); for (let i = 0; i < rows; i++) { for (let j = 0; j < cols; j++) { prefix[i + 1][j + 1] = matrix[i][j] + prefix[i][j + 1] + // сверху prefix[i + 1][j] - // слева prefix[i][j]; // вычитаем дважды учтённый угол } } return prefix; } // сумма прямоугольника (r1, c1) .. (r2, c2) включительно function regionSum(prefix, r1, c1, r2, c2) { return ( prefix[r2 + 1][c2 + 1] - prefix[r1][c2 + 1] - prefix[r2 + 1][c1] + prefix[r1][c1] ); }
Это формула включений-исключений: вычли верхнюю полосу, вычли левую полосу, вернули дважды вычтенный угол. Подготовка — O(rows·cols), каждый запрос — O(1).
Обратная задача: разностный массив
Есть зеркальная техника для случая, когда много обновлений и мало запросов. Например: «прибавь 5 ко всем элементам с 2 по 7» — и таких операций тысячи.
Вместо того чтобы честно проходить по отрезку, отмечаем только границы:
function applyRanges(length, updates) { const diff = new Array(length + 1).fill(0); for (const [l, r, value] of updates) { diff[l] += value; diff[r + 1] -= value; } // накопленная сумма превращает разности в реальные значения const result = []; let running = 0; for (let i = 0; i < length; i++) { running += diff[i]; result.push(running); } return result; } applyRanges(5, [[1, 3, 2], [0, 2, 1]]); // [1, 3, 3, 2, 0]
Каждое обновление — O(1), финальная сборка — O(n). Если обновлений много, выигрыш огромный.
Когда применять
Признаки задачи на префиксные суммы:
- нужно много раз считать сумму (или произведение, XOR, количество) на отрезках;
- ищется подмассив с заданной суммой, и в массиве есть отрицательные числа;
- нужно посчитать что-то «слева» и «справа» от каждой позиции;
- много интервальных обновлений при редких чтениях — тогда разностный массив.
Приём обобщается не только на сумму. Префиксный XOR решает задачи про подмассивы с нулевым XOR, префиксное произведение — задачу «произведение всех элементов кроме текущего», префиксный счётчик — «сколько гласных на отрезке».
Что запомнить
- Подготовка за O(n) даёт ответы на запросы суммы за O(1).
- Фиктивный ноль в начале избавляет от краевых случаев.
- Связка «префиксная сумма + хеш-таблица» решает задачи про подмассивы с заданной суммой за O(n) и работает с отрицательными числами, где скользящее окно бессильно.
- Двумерный вариант считается по формуле включений-исключений.
- Разностный массив — обратная техника для частых интервальных обновлений.
Закрепите на практике
Хорошая задача для тренировки — произведение всех элементов массива кроме текущего. Она решается ровно этой идеей, только вместо сумм используются префиксные и суффиксные произведения, а деление запрещено условием.
Решай алгоритмические задачи как профи
