Префиксные суммы: что это такое и как использовать

Префиксные суммы

Префиксные суммы - это методика обработки последовательности чисел, где каждый элемент последовательности представляет собой сумму всех предыдущих элементов, включая сам элемент. Этот подход позволяет эффективно вычислять сумму любого подмассива последовательности за константное время.

Для наглядности рассмотрим следующую задачу. Дан массив чисел [1, 2, 3, 4, 5]. Нам необходимо вычислить сумму всех чисел в подмассиве, начинающемся с индекса 1 и заканчивающемся индексом 3.

Без использования префиксных сумм мы были бы вынуждены проходить по элементам от 1 до 3 и суммировать их по очереди. Однако с помощью префиксных сумм мы можем решить эту задачу за константное время.

Сначала создадим новый массив prefix, в котором каждый элемент будет хранить сумму всех чисел до текущей позиции в исходном массиве. Для нашего примера, массив prefix будет выглядеть следующим образом: [0, 1, 3, 6, 10]. Здесь первый элемент равен нулю, а каждый следующий элемент равен сумме предыдущего элемента и числа из исходного массива.

Теперь, чтобы вычислить сумму чисел в подмассиве, начинающемся с индекса 1 и заканчивающемся индексом 3, мы можем просто вычесть из элемента prefix[4] элемент prefix[0]. Это работает, потому что prefix[4] содержит сумму всех чисел в исходном массиве, а prefix[0] равно нулю. Полученная разница будет являться искомой суммой.

Давайте рассмотрим пример кода на языке Python, который реализует вычисление префиксных сумм:

def prefix_sum(arr):
    n = len(arr)
    prefix = [0] * (n + 1)
    for i in range(1, n + 1):
        prefix[i] = prefix[i - 1] + arr[i - 1]
    return prefix

def subarray_sum(prefix, start, end):
    return prefix[end + 1] - prefix[start]

# Пример использования
arr = [1, 2, 3, 4, 5]
prefix = prefix_sum(arr)
start = 1
end = 3
result = subarray_sum(prefix, start, end)
print(result) # Вывод: 9

В этом примере мы определяем две функции: prefix_sum, которая вычисляет массив префиксных сумм, и subarray_sum, которая вычисляет сумму чисел в заданном подмассиве. Затем мы используем эти функции для решения нашей исходной задачи.

Использование префиксных сумм позволяет нам значительно сократить время выполнения вычислений суммы подмассива, особенно при работе с большими массивами. Этот подход является эффективным и удобным, особенно в задачах, требующих частого обновления или вычисления суммы подмассивов.