Prefix sum

Info

Подход "Prefix sum" (префиксные суммы) является широко используемым методом в алгоритмах для эффективного вычисления сумм элементов в подмассивах или подматрицах. Основная идея заключается в предварительном вычислении сумм, чтобы можно было быстро находить суммы произвольных подмассивов или подматриц без необходимости каждый раз пересчитывать их заново.

Преимущества

• Эффективность: Вычисление сумм подмассивов или подматриц происходит за O(1) после предварительного вычисления префиксных сумм.
• Универсальность: Подход можно применять к различным задачам, связанным с суммами подмассивов или подматриц.

Основные понятия

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

• Префиксная сумма prefixSum[i] для массива arr — это сумма всех элементов от начала массива до индекса i (включительно).
• Формально, prefixSum[i] = arr[0] + arr[1] + ... + arr[i].

Использование префиксных сумм:

• Сумма элементов подмассива arr[i:j] (от индекса i до индекса j, включительно) может быть вычислена как prefixSum[j] - prefixSum[i-1] (если i > 0), или как prefixSum[j] (если i == 0).

Пример в массиве

Рассмотрим массив arr = [1, 2, 3, 4, 5].

Вычисление префиксных сумм:

• prefixSum[0] = 1
• prefixSum[1] = 1 + 2 = 3
• prefixSum[2] = 1 + 2 + 3 = 6
• prefixSum[3] = 1 + 2 + 3 + 4 = 10
• prefixSum[4] = 1 + 2 + 3 + 4 + 5 = 15

Как это использовать

Использование префиксных сумм для вычисления сумм подмассивов:

• Сумма подмассива arr[1:3] (элементы с индексами 1, 2, 3):

• • prefixSum[3] - prefixSum[0] = 10 - 1 = 9

• Сумма подмассива arr[0:2] (элементы с индексами 0, 1, 2):

• • prefixSum[2] - prefixSum[-1] = 6 - 0 = 6 (здесь prefixSum[-1] считается равным 0, так как это начало массива)

Пример в матрице

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

1. Вычисление префиксных сумм для каждой строки:

• • Для каждой строки matrix[i] вычисляем префиксные суммы.

2. Использование префиксных сумм для вычисления сумм подматриц:

• • Для каждой пары столбцов (left, right) вычисляем суммы строк между этими столбцами.
• • Для каждого набора сумм строк вызываем функцию, которая находит максимальную сумму подмассива, не превышающую k.