Информатика · ЕГЭ · 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, а не остановиться перед ним.
| Шаг | Результат |
|---|---|
| a | 4, 1, 7, 2 |
| p | 0, 4, 5, 12, 14 |
| Индексы 1…3 | 14 − 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].
Попробовать на Алгосе
Программирование для ЕГЭ
Продолжи подготовку в курсе: разбирай способы решения и проверяй их на самостоятельных заданиях.
Перейти к курсу Все курсы