Prefix sum — это массив накопленных сумм.
То есть вместо того, чтобы каждый раз заново считать сумму на отрезке, мы заранее строим вспомогательный массив, где в каждой позиции хранится:
сумма всех элементов от начала массива до этой позиции.
Например, есть массив:
a = [3, 1, 4, 2, 5]
Prefix sum будет:
prefix = [3, 4, 8, 10, 15]
Потому что:
prefix[0] = 3
prefix[1] = 3 + 1 = 4
prefix[2] = 3 + 1 + 4 = 8
prefix[3] = 3 + 1 + 4 + 2 = 10
prefix[4] = 3 + 1 + 4 + 2 + 5 = 15
Главная сила prefix sum в том, что можно быстро считать сумму любого отрезка.
Например, нужно узнать сумму элементов с индекса 1 по индекс 3:
a[1] + a[2] + a[3] = 1 + 4 + 2 = 7
Через prefix sum:
sum(1..3) = prefix[3] - prefix[0]
= 10 - 3
= 7
То есть формула такая:
sum(l..r) = prefix[r] - prefix[l - 1]
Если l = 0, то просто:
sum(0..r) = prefix[r]
Часто делают prefix-массив на один элемент длиннее, чтобы не обрабатывать отдельно случай l = 0:
a = [3, 1, 4, 2, 5]
prefix = [0, 3, 4, 8, 10, 15]
Тогда:
prefix[i] = сумма первых i элементов
И сумма отрезка [l, r) — то есть от l включительно до r не включительно:
sum(l..r-1) = prefix[r] - prefix[l]
Например:
sum элементов с индекса 1 до 3 включительно
Это диапазон [1, 4):
prefix[4] - prefix[1] = 10 - 3 = 7
На JavaScript:
const a = [3, 1, 4, 2, 5];
const prefix = [0];
for (let i = 0; i < a.length; i++) {
prefix[i + 1] = prefix[i] + a[i];
}
console.log(prefix); // [0, 3, 4, 8, 10, 15]
function rangeSum(l, r) {
// сумма от l до r включительно
return prefix[r + 1] - prefix[l];
}
console.log(rangeSum(1, 3)); // 7
Смысл прям очень практичный:
обычная сумма отрезка занимает O(n), потому что надо пройти по элементам.
С prefix sum после подготовки каждый запрос суммы занимает O(1).
То есть:
подготовка prefix sum: O(n)
каждый запрос суммы: O(1)
Это один из базовых приёмов в алгоритмах: когда много запросов на суммы по диапазонам, prefix sum превращает повторный пересчёт в мгновенное вычитание.
