Алгоритмы с нуля

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

Суть Предвычисли префиксный массив раз. Потом любой запрос суммы диапазона стоит O(1) вычитанием вместо O(n) проходом. Меняем O(n) памяти на мгновенные ответы.

◷ 18 min

У тебя есть массив чисел и поток вопросов: «Какая сумма элементов от индекса 3 до 7?» потом «Какая сумма от индекса 1 до 4?» потом «От 5 до 9?» Считать каждую сумму проходом подмассива стоит O(n) за запрос. Но что если ты предвычислишь накопленную сумму на каждой позиции? Тогда ты ответишь на каждый запрос за O(1) вычитанием. Ты платишь O(n) времени раз, чтобы собрать префиксный массив, и потом получишь O(1) за запрос навечно. Это приём префиксных сумм.

Цель

После этого урока ты сможешь узнавать, когда задача на диапазонные запросы выигрывает от префиксных сумм, собирать префиксный массив за O(n) времени, отвечать на запросы сумм диапазона за O(1) вычитанием, разобраться в уходе за off-by-one (используя префиксный массив длины n+1), и видеть, как та же идея обобщается на префиксные счётчики и 2D сетки.

Идея

Префиксная сумма — техника предвычисления, где ты собираешь массив, что хранит накопленную сумму от начала массива до каждого индекса.

Задача без префиксных сумм:

Дан массив arr = [2, 5, 1, 3, 4], ты получаешь много запросов на суммы диапазонов. Например:

Сумма от индекса 1 до 3? Ты проходишь и считаешь arr[1] + arr[2] + arr[3] = 5 + 1 + 3 = 9.
Сумма от индекса 0 до 2? Ты проходишь и считаешь arr[0] + arr[1] + arr[2] = 2 + 5 + 1 = 8.

Каждый запрос стоит O(n) в худшем случае. С q запросами итого O(n × q). Это масштабируется плохо.

Идея: предвычисли накопленные суммы

Собери префиксный массив prefix длины n+1 (не n, а n+1!), где:

prefix[0] = 0 (сумма нулевых элементов)
prefix[1] = arr[0] (сумма первых 1 элемента)
prefix[2] = arr[0] + arr[1] (сумма первых 2 элементов)
prefix[k] = arr[0] + arr[1] + ... + arr[k-1] (сумма первых k элементов)

Для arr = [2, 5, 1, 3, 4] префиксный массив это:

prefix = [0, 2, 7, 8, 11, 15]

Теперь, чтобы найти сумму элементов от индекса i до j (включительно), используй эту формулу:

sum(i, j) = prefix[j+1] - prefix[i]

Почему? Потому что:

prefix[j+1] = сумма первых j+1 элементов = arr[0] + … + arr[j]
prefix[i] = сумма первых i элементов = arr[0] + … + arr[i-1]
Вычитаем: arr[i] + arr[i+1] + … + arr[j]

Пример:

Сумма от индекса 1 до 3: prefix[4] - prefix[1] = 11 - 2 = 9 ✓
Сумма от индекса 0 до 2: prefix[3] - prefix[0] = 8 - 0 = 8 ✓

Уход за off-by-one:

Ключ в том, чтобы использовать префиксный массив длины n+1 (не n). Так prefix[i] всегда представляет сумму первых i элементов, и формула sum(i, j) = prefix[j+1] - prefix[i] работает чисто на всех краях без особых случаев.

Обмен времени и памяти:

Подготовка: O(n) времени на сборку префиксного массива.
Память: O(n) дополнительной памяти на префиксный массив.
За запрос: O(1) времени.
Итого для q запросов: O(n + q) вместо O(n × q).

Это классический приём предвычисления: потратишь время и память один раз заранее, потом переиспользуешь результат много раз даром. Ты видел похожую идею в two-pointer и sliding window (двигаешься инкрементально, чтобы не пересчитывать). Здесь ты предвычисляешь, чтобы превратить повторную работу в мгновенные поиски.

Код

Давай кодировать приём префиксных сумм.

1. Собери префиксный массив:

function buildPrefix(arr) {
  const n = arr.length;
  const prefix = new Array(n + 1).fill(0);
  
  for (let i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] + arr[i];
  }
  
  return prefix;
}

2. Отвечай на запросы сумм диапазонов:

function rangeSum(prefix, i, j) {
  // Сумма элементов от индекса i до j (включительно)
  return prefix[j + 1] - prefix[i];
}

Полный пример:

const arr = [2, 5, 1, 3, 4];
const prefix = buildPrefix(arr);

console.log(prefix);  // [0, 2, 7, 8, 11, 15]
console.log(rangeSum(prefix, 1, 3));  // 5 + 1 + 3 = 9
console.log(rangeSum(prefix, 0, 2));  // 2 + 5 + 1 = 8
console.log(rangeSum(prefix, 0, 4));  // 2 + 5 + 1 + 3 + 4 = 15
console.log(rangeSum(prefix, 2, 4));  // 1 + 3 + 4 = 8

Попробуй запустить это:

Вывод

Пошаговый разбор

Давай трассировать сборку префиксного массива для [2, 5, 1, 3, 4]:


      1
      function buildPrefix(arr) {
    

      2
        const prefix = new Array(arr.length + 1).fill(0);
    

      3
        for (let i = 0; i < arr.length; i++) {
    

      4
          prefix[i + 1] = prefix[i] + arr[i];
    

      5
        }
    

      6
        return prefix;
    

      7
      }

Теперь трассируй запрос суммы диапазона. Найди сумму от индекса 1 до 3:


      1
      function rangeSum(prefix, i, j) {
    

      2
        return prefix[j + 1] - prefix[i];
    

      3
      }

Сложность

Операция	Время	Память	Замечания
Собери префиксный массив	O(n)	O(n)	Однопроход, накопляй сумму
Запрос суммы диапазона	O(1)	O(1)	Два поиска и одно вычитание
Итого q запросов	O(n + q)	O(n)	Подготовка раз, запросы много раз

Сравнение с наивным подходом:

Подход	Время подготовки	За запрос	Итого для q запросов
Наивный (проход каждого запроса)	O(1)	O(n)	O(n × q)
Префиксная сумма	O(n)	O(1)	O(n + q)

Если q большой (много запросов), префиксные суммы выигрывают в огромной мере. Если q = 1000 и n = 100, наивный это 100 000 операций; префиксная сумма это 1 100 операций. Почти 100× быстрее.

Когда это стоит?

Используй префиксные суммы, если:

Ты имеешь много запросов сумм диапазонов на одном массиве.
Массив не меняется (статический).

Не используй, если:

Ты имеешь только один или два запроса.
Массив меняется часто (ты должен пересобрать prefix при каждом изменении, стоит O(n)).

Практика 0 / 5

Собери префиксный массив для [3, 1, 4, 1, 5]. Что такое prefix[3]?

Используя префиксный массив [0, 3, 4, 8, 9, 14] (из массива [3, 1, 4, 1, 5]), какова сумма от индекса 1 до 3?

Почему мы создаём префиксный массив длины n+1 вместо n?

Массив имеет 10 000 элементов. Ты будешь отвечать на 5 000 запросов сумм диапазонов. Примерно насколько раз быстрее наивный подход с префиксными суммами за запрос?

Если исходный массив меняется (например, ты обновляешь arr[3]), что происходит с префиксным массивом?

Частая ошибка

Off-by-one индексирование. Самая частая ошибка: путаница в том, какой индекс префиксного массива использовать. Помни: prefix[k] = сумма первых k элементов (индексы 0 до k-1). Чтобы запросить сумму от индекса i до j, вычти prefix[j+1] - prefix[i]. Если ты используешь prefix[j] - prefix[i-1], ты получишь неправильный результат. Всегда рисуй это с маленьким примером сначала.

Граничные случаи

Запрос от индекса 0. Если ты хочешь сумму от индекса 0 до j (начало массива), формула это prefix[j+1] - prefix[0]. Поскольку prefix[0] = 0, это упрощается до prefix[j+1], что правильно. Нуль в начале обрабатывает этот граничный случай автоматически.

Проверь себя

Викторина

Почему техника префиксной суммы хороший пример обмена времени и памяти, что ты учил в Big-O?

Итог

Техника префиксной суммы предвычисляет накопленные суммы чтобы отвечать на запросы сумм диапазонов за O(1).

Ключевые факты:

Префиксный массив: prefix[k] = сумма первых k элементов (arr[0] до arr[k-1]). Инициализируй prefix[0] = 0. Собери за O(n) времени.
Формула суммы диапазона: сумма элементов от индекса i до j = prefix[j+1] - prefix[i]. Это работает благодаря нулю в начале.
Почему это работает: Вычитание двух накопленных сумм отменяет часть до индекса i, оставляя только часть от i до j.
Обмен времени и памяти: Потратишь O(n) времени и O(n) памяти на сборку. Потом каждый запрос это O(1). Итого для q запросов: O(n + q) вместо O(n × q).
Когда использовать: Много запросов на статический массив. Если массив меняется, ты должен пересобрать.
Обобщение: Та же идея расширяется на префиксные счётчики (как много элементов в диапазоне удовлетворяют условие?), 2D префиксные суммы (суммы прямоугольных областей), и больше. Паттерн всегда тот же: предвычисли раз, переиспользуй навечно.

Дальше ты будешь исследовать хеширование (сохранение и получение значений по ключу за O(1)) и потом структуры данных как стеки и очереди.

Продолжить восхождение ↑Работа на месте