re:re:actable
Урок 033 минуты чтения

Что такое prefix sums?

На этой странице
Кратко

Prefix sums - техника, где заранее считаются суммы префиксов массива, чтобы быстро получать сумму любого подмассива. Она полезна для range queries, subarray sum и задач с частыми запросами суммы.

Вопрос

Что такое prefix sums и как они дают сумму диапазона за O(1)?

Идея

Для массива:

nums = [2, 4, 1, 3]

Prefix:

prefix = [0, 2, 6, 7, 10]

prefix[i] - сумма первых i элементов. Сумма nums[l..r]:

prefix[r + 1] - prefix[l]

Например, сумма nums[1..2] = 4 + 1 = 5:

prefix[3] - prefix[1] = 7 - 2 = 5

Мы из суммы первых трех элементов вычитаем сумму первого - остаются ровно элементы с 1 по 2. Ноль в начале prefix нужен, чтобы формула работала и для диапазонов, начинающихся с индекса 0.

Реализация

function buildPrefix(nums: number[]): number[] {
  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: number[], left: number, right: number): number {
  return prefix[right + 1] - prefix[left]
}

Subarray sum equals K

function subarraySum(nums: number[], k: number): number {
  const count = new Map<number, number>()
  count.set(0, 1)
 
  let prefix = 0
  let answer = 0
 
  for (const num of nums) {
    prefix += num
    answer += count.get(prefix - k) ?? 0
    count.set(prefix, (count.get(prefix) ?? 0) + 1)
  }
 
  return answer
}

Как это работает. Сумма подмассива от j до i равна prefix(i) - prefix(j - 1). Мы хотим, чтобы она была k, то есть ищем раньше встречавшийся префикс, равный prefix - k. Map хранит, сколько раз встречался каждый префикс. Начальная запись 0 -> 1 - это пустой префикс, нужный для подмассивов, начинающихся с индекса 0.

Пример: nums = [1, 2, 3], k = 3.

numprefixИщем prefix - kНайдено разanswercount после
11-200{0:1, 1:1}
23011{0:1, 1:1, 3:1}
36312{0:1, 1:1, 3:1, 6:1}

Ответ 2: подмассивы [1, 2] и [3]. В отличие от sliding window, этот прием работает и с отрицательными числами.

Что отвечать на собеседовании?

Prefix sums хранят сумму элементов от начала до каждой позиции. Тогда сумма диапазона считается за O(1) через разность двух префиксов. Для задач на количество подмассивов с суммой k используют Map частот prefix sums.

Что важно помнить: частые ошибки

  • Делать prefix без начального 0.
  • Ошибаться в индексах right + 1.
  • Применять sliding window к массивам с отрицательными числами, где нужен prefix + Map.
  • Не учитывать переполнение в языках с fixed int.
  • Забывать space O(n) или O(k) для Map.

Мини-шпаргалка

  • prefix[0] = 0.
  • prefix[i + 1] = prefix[i] + nums[i].
  • Sum [l, r] = prefix[r + 1] - prefix[l].
  • Prefix + Map решает subarray sum.
  • Хорош для range queries.
  • Работает с отрицательными числами.

Документация

Wikipedia: Prefix sum.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам