Prefix Sums (Префиксные суммы)

Префиксные суммы (Prefix Sums)

Префиксные суммы — это техника предподсчета, позволяющая за O(1) вычислять сумму элементов на любом подотрезке массива. Основная идея: заранее посчитать суммы от начала массива до каждого индекса.

📝 Определение

Пусть дан массив nums длины $N$. Массив префиксных сумм prefix (обычно длины $N+1$) определяется так:

$$\text{prefix}[i]=\sum _{k=0}^{i-1}\text{nums}[k]$$

То есть:

• prefix[0] = 0 (базовый случай, сумма пустого подмассива)
• prefix[1] = nums[0]
• prefix[2] = nums[0] + nums[1]
• …
• prefix[i] = nums[0] + ... + nums[i-1]

Важно: Часто удобно делать prefix на 1 элемент длиннее nums, чтобы prefix[0] был равен 0. Это упрощает формулы (не нужно обрабатывать случай L=0 отдельно).

🚀 Зачем это нужно?

Главное преимущество — быстрое вычисление суммы подмассива (Range Sum Query).

Формула суммы на отрезке $[L,R]$

Чтобы найти сумму элементов от индекса $L$ до $R$ (включительно):

$$\text{Sum}(L,R)=\text{prefix}[R+1]-\text{prefix}[L]$$

Почему это работает? prefix[R+1] — это сумма nums[0]...nums[R]. prefix[L] — это сумма nums[0]...nums[L-1]. Вычитая из первой суммы вторую, мы “отрезаем” начальную часть, оставляя только nums[L]...nums[R].

---

💻 Примеры

1. Визуализация

Пусть nums = [3, 1, 4, 2, 5]

Index	0	1	2	3	4	5
nums	3	1	4	2	5	-
prefix	0	3	4	8	10	15

Пример вычисления: Сумма подмассива nums[1..3] (элементы 1, 4, 2): Sum(1, 3) = prefix[4] - prefix[1] = $10-3=7$ Проверка: $1+4+2=7$ ✅

2. Реализация на JavaScript

/**
 * @param {number[]} nums
 * @return {number[]}
 */
function buildPrefixSum(nums) {
    const n = nums.length;
    // Создаем массив на 1 больше, заполненный нулями
    const prefix = new Array(n + 1).fill(0);
    
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    
    return prefix;
}
 
/**
 * @param {number[]} prefix - Массив префиксных сумм
 * @param {number} left - Начальный индекс
 * @param {number} right - Конечный индекс
 * @return {number}
 */
function getRangeSum(prefix, left, right) {
    return prefix[right + 1] - prefix[left];
}
 
// Использование
const nums = [1, 2, 3, 4, 5];
const P = buildPrefixSum(nums);
console.log(getRangeSum(P, 1, 3)); // 9  (nums[1]+nums[2]+nums[3] = 2+3+4)

⚙️ Сложность

Операция	Временная сложность	Пространственная сложность
Построение (Build)	$O(N)$	$O(N)$
Запрос (Query)	$O(1)$	$O(1)$

Практика

• Задачи LeetCode — раздел «Стек и очереди» (Range Sum Query и др.)
• array