Префиксные суммы - Алгоритмика

Определение. Префиксными суммами массива

[a_0, a_1, a_2, \ldots, a_{n - 1}]

называется массив

[s_0, s_1, s_2, \ldots, s_n]

, определенный следующим образом:

\begin{aligned} & s_0 = 0\\ & s_1 = a_0\\ & s_2 = a_0 + a_1\\ & s_3 = a_0 + a_1 + a_2\\ & \ldots\\ & s_n = a_0 + a_1 + \ldots + a_{n - 1} \end{aligned}

Обратите внимание, что в такой индексации

$s_k$ равен сумме первых $k$ элементов массива $a$ не включая $a_k$ ,
длина $s$ на единицу больше длины $a$ ,
$s_0$ всегда равен нулю.

Иногда префиксные суммы определяют включая правый конец и без нулевого элемента, то есть как $s_k = a_0 + a_1 + \ldots + a_k$ , но по той же причине, почему отрезки почти всегда менее удобны, чем полуинтервалы, мы всегда будем работать с «полуинтрвальными» префиксными суммами из определения.

Формулу для $s_k$ можно записать рекуррентно как $s_{k+1} = s_k + a_k$ , что сразу дает метод подсчета префиксных сумм за линейное время:

int s[n + 1];

s[0] = 0;

for (int i = 0; i < n; i++)
    s[i + 1] = s[i] + a[i];

Задача. Дан массив целых чисел, и приходят запросы вида «найти сумму на полуинтервале с позиции $l$ до позиции $r$ ». Нужно отвечать на запросы за $O(1)$ .

Предподсчитаем перед ответами на запросы массив префиксных сумм для исходного массива. Тогда если бы во всех запросах $l$ было равно нулю, то ответом на запрос была бы просто префиксная сумма $s_r$ . Но как действовать, если $l \neq 0$ ?

В префиксной сумме $s_r$ содержатся все нужные нам элементы, однако есть еще лишние, а именно $a_0, a_1, \ldots, a_{l - 1}$ . Заметим, что такая сумма в свою очередь равна уже посчитанной префиксной сумме $s_l$ . Таким образом, выполнено тождество:

a_{l} + a_{l + 1} + \ldots + a_{r - 1} = s_{r} - s_{l}

Для ответа на запрос поиска суммы на произвольном полуинтервале нужно просто вычесть друг из друга две предподсчитанные префиксные суммы.

#Другие операции

Подобный прием можно использовать не только для сложения, но и для других операций.

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

Помимо сложения, есть и другие операции, которые являются обратимыми:

побитовое исключающее «или», также известное как xor и обозначаемое $\oplus$ ,
сложение по модулю,
умножение и умножение по модулю (обратное — деление).

Помимо обычной суммой, самая популярная из них — xor, которая считается ещё проще:

a_l \oplus a_{l + 1} \oplus \ldots \oplus a_{r - 1} = s_r \oplus s_l

#Задачи на префиксные суммы

Задача. Дан массив целых чисел. Определите, есть ли в нём подотрезок заданной суммы за линейное время.

Задача. Даны два массива одинаковой длины. Найдите такой подотрезок, что сумма элементов первого массива совпадала с суммой элементов второго массива (на индексах этого отрезка).

Задача. Дано мультимножество из $n$ целых чисел. Найдите любое его подмножество, сумма чисел которого делится на $n$ .