Информатика · ЕГЭ · 4 мин чтения

Как префиксные суммы ускоряют поиск суммы на отрезке?

Редакция Алгоса · Обновлено

Короткий ответ

Префиксная сумма — сумма элементов от начала списка до выбранной границы. Удобно хранить p[k] как сумму первых k элементов и начать с p[0] = 0. Тогда сумма элементов с индексами от l до r включительно равна p[r + 1] − p[l]. Вычитание убирает всё, что находилось перед нужным участком.

Разберись, что нужно найти

Пусть список a равен [4, 1, 7, 2]. Накопленные суммы p будут [0, 4, 5, 12, 14]. Здесь p[3] = 12 относится к первым трём элементам 4, 1, 7. Индекс в массиве сумм описывает количество уже взятых элементов, поэтому длина p на единицу больше длины исходного списка.

Связь условия задачи с нужным действием
Что дано или требуетсяКак это использовать
p[0]Сумма нуля элементов: 0
p[k]Сумма первых k элементов
Участок l…r включительноp[r + 1] − p[l]

Проследи решение на конкретных данных

Хотим сумму с индекса 1 до индекса 3 включительно: это 1 + 7 + 2. В p[4] содержится весь список, а p[1] содержит только элемент перед нужным участком. Вычитаем 14 − 4 = 10. Сдвиг r + 1 нужен, чтобы включить элемент с индексом r, а не остановиться перед ним.

Промежуточные результаты разобранного примера
ШагРезультат
a4, 1, 7, 2
p0, 4, 5, 12, 14
Индексы 1…314 − 4 = 10
Пример с объяснением
Построение на Python:
a = [4, 1, 7, 2]
p = [0]
for x in a:
    p.append(p[-1] + x)
l, r = 1, 3
print(p[r + 1] - p[l])
Вывод равен 10. Запись p[-1] берёт последний уже вычисленный итог; append добавляет следующий итог в конец списка.

Проверь границы способа и реши сам

Один раз построив p за проход по списку, можно отвечать на много запросов двумя обращениями и вычитанием. Отрицательные элементы способу не мешают: одинаковая начальная часть всё равно вычитается. Но если сам список изменился, прежние суммы могут стать неверными. Этот вариант рассчитан на неизменяемый после подготовки набор данных.

Самопроверка: для [5, −2, 4, 3] построй p и найди сумму от индекса 1 до индекса 2 включительно. Затем найди сумму одного элемента с индексом 0. Проверь ответы обычным сложением, чтобы убедиться в правильности границ.

Ответ и почему так

Получаем p = [0, 5, 3, 7, 10]. Нужный участок имеет сумму p[3] − p[1] = 7 − 5 = 2, совпадающую с −2 + 4. Для одного первого элемента берём p[1] − p[0] = 5. Начальный ноль избавляет от отдельного случая левой границы.

Что запомнить

Если p[k] хранит первые k элементов, сумма участка l…r включительно равна p[r + 1] − p[l].

Попробовать на Алгосе

Программирование для ЕГЭ

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

Перейти к курсу Все курсы

Источники и материалы

Разобраться дальше

Все вопросы и разборы