Префиксная сумма

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

Суть метода заключается в создании дополнительного массива, где каждый элемент хранит сумму всех элементов исходного массива от начала до текущего индекса (то есть на «префиксе»).

----------------------------------------

1. Одномерные префиксные суммы (1D Prefix Sums)

Это классический и самый популярный вид.

Построение:
Пусть у нас есть исходный массив A из N элементов. Создадим массив префиксных сумм P размером N+1 (удобнее делать индексацию с 1, а P[0] = 0).
Формула вычисления: P[i] = P[i-1] + A[i-1]

Пример:

• Исходный массив A = [3, 1, 4, 1, 5]
• Префиксный массив P = [0, 3, 4, 8, 9, 14]

(где P[0]=0, P[1]=3, P[2]=3+1=4, P[3]=4+4=8 и т.д.)

Запрос (Сумма на отрезке):
Чтобы найти сумму элементов исходного массива с индекса L по индекс R (включительно), не нужно перебирать их циклом. Достаточно использовать формулу:
Sum(L, R) = P[R+1] - P[L]

Пример запроса: Сумма элементов со 2-го по 4-й (это 4+1+5 = 10). Считаем: P[5] - P[2] = 14 - 4 = 10.

----------------------------------------

1. Виды и вариации префиксных сумм

Хотя концепция родилась из сложения чисел в одномерном массиве, её логика применяется шире. Вот основные виды и расширения этого метода:

А. Двумерные префиксные суммы (2D Prefix Sums)
Используются для работы с матрицами. Позволяют за O(1) узнать сумму чисел в любом прямоугольнике внутри матрицы.

• Построение: Каждый элемент P[i][j] хранит сумму элементов в прямоугольнике от левого верхнего угла (0,0) до правого нижнего (i,j).

Формула: P[i][j] = A[i][j] + P[i-1][j] + P[i][j-1] - P[i-1][j-1] (вычитаем пересечение, чтобы не посчитать его дважды).

• Запрос: Сумма в прямоугольнике с углами (x1, y1) и (x2, y2) вычисляется как:

Sum = P[x2][y2] - P[x1-1][y2] - P[x2][y1-1] + P[x1-1][y1-1]

Б. Многомерные префиксные суммы (3D, k-D)
Работает по тому же принципу включений-исключений для трехмерного пространства (кубов) и пространств более высоких размерностей. Формулы становятся длиннее, но сложность запроса остается O(1).

В. Префиксные массивы для других операций
Идея префиксов работает не только для суммы (сложения), но и для любой ассоциативной и обратимой операции.

• Префиксное произведение: P[i] = P[i-1] * A[i]. Произведение на отрезке [L, R] равно P[R] / P[L-1]. (Осторожно: не работает, если в массиве есть нули, требует отдельной логики).
• Префиксный XOR (исключающее ИЛИ): Популярно в криптографии и задачах по программированию. Обратная операция для XOR — это сам XOR. Поэтому XOR на отрезке [L, R] = P[R] ^ P[L-1].

(Важно: префиксные массивы НЕ работают с операциями максимума или минимума, так как для них нет обратной операции. Из минимума префикса нельзя "вычесть" другой минимум).

Г. Массив разностей (Difference Array)
Это «обратная» структура к префиксным сумм. Если префиксная сумма помогает быстро читать диапазоны, то массив разностей помогает быстро изменять диапазоны.

• Если нужно K раз прибавить число X ко всем элементам от L до R, обычный цикл займёт O(K * N).
• С массивом разностей D мы делаем два действия за O(1): D[L] += X и D[R+1] -= X.
• В конце мы строим префиксную сумму от массива D, чтобы получить итоговый измененный массив за O(N).

----------------------------------------
Ограничения префиксных сумм

Главный минус стандартных префиксных сумм — они статичны.
Если исходный массив A изменится (например, вы замените A[3] = 10), вам придется пересчитывать весь префиксный массив P справа от этого элемента, что займет O(N) времени.

Динамические альтернативы:
Если вам нужно чередовать операции "изменить элемент" и "узнать сумму на отрезке", обычные префиксные суммы не подойдут. Вместо них используются более продвинутые структуры данных:

1. Дерево Фенвика (Fenwick Tree / Binary Indexed Tree) — позволяет и изменять элемент, и находить префиксную сумму за O(log N).
2. Дерево отрезков (Segment Tree) — также работает за O(log N), но более универсально (позволяет находить максимумы/минимумы).