Задания № 17, 24 · ЕГЭ

Сумма на отрезке

Как быстро находить сумму элементов между двумя индексами

2 мин чтенияСложность: Обновлено 29 сентября 2026

Сумма на отрезке — это сумма элементов массива, расположенных между двумя заданными границами. Для частого вычисления таких сумм используют кумулятивную сумму, также называемую префиксной суммой.

Сумма на отрезке

Сумма на отрезке $[l; r]$ — это сумма элементов массива с индексами от $l$ до $r$ включительно, где $l \le r$. В задачах важно заранее определить, являются ли границы включительными: обычно отрезок массива включает оба элемента $a_l$ и $a_r$.

Формула

Если элементов немного, сумму можно получить последовательным сложением. При большом количестве запросов удобнее один раз построить массив префиксных сумм $P$, где $P_i$ — сумма элементов от начала массива до позиции $i включительно.

\[P_i = a_1 + a_2 + \dots + a_i, \qquad S(l,r)=P_r-P_{l-1}.\]

Для отрезка, начинающегося с первого элемента, используется отдельный случай: $S(1,r)=P_r$. В программировании часто добавляют нулевой элемент $P_0=0$. Тогда формула становится единой: $S(l,r)=P_r-P_{l-1}$.

№

Пример

Пусть массив равен $[4, 7, 2, 5, 3]$. Нужно найти сумму на отрезке $[2;4]$: $7+2+5=14$. Префиксные суммы: $P=[0,4,11,13,18,21]$. Поэтому $S(2,4)=P_4-P_1=18-4=14$.

Не перепутайте границы

Сумма на отрезке $[l;r]$ включает оба конца. Ошибка возникает, если вычесть $P_l$ вместо $P_{l-1}$: тогда элемент с индексом $l$ будет потерян. Также не следует путать сумму на отрезке с количеством элементов на отрезке: количество равно $r-l+1$, а сумма зависит от значений элементов.

Проверьте себя

Префиксные суммы равны $P_0=0$, $P_1=6$, $P_2=10$, $P_3=15$. Чему равна сумма на отрезке $[2;3]$?

Построение префиксных сумм занимает $O(n)$ времени, а получение одной суммы на отрезке — $O(1)$. Поэтому метод особенно полезен, когда нужно обработать много запросов к одному массиву. Общая работа с такими диапазонами рассматривается в статье обработка отрезка массива, а сами запросы — на странице запросы к массиву.

Главное за минуту

Главное

Сумма на отрезке $[l;r]$ включает элементы с индексами от $l$ до $r$.
При префиксных суммах используется формула $S(l,r)=P_r-P_{l-1}$.
Префиксные суммы позволяют отвечать на каждый запрос за $O(1)$ после подготовки массива.

Формула

Префиксные суммы равны \(P_0=0\), \(P_1=6\), \(P_2=10\), \(P_3=15\). Чему равна сумма на отрезке \([2;3]\)?

Главное