Задание № 12 · ЕГЭ

Суффиксные суммы

Массив сумм элементов от текущей позиции до конца

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

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

Суффиксные суммыСуффикс — конечная часть последовательности.

Для массива \(a\) длины \(n\) массив суффиксных сумм \(s\) задаётся так: \(s_i=a_i+a_{i+1}+\dots+a_{n-1}\). Индексы здесь начинаются с нуля. Последняя суффиксная сумма равна последнему элементу исходного массива: \(s_{n-1}=a_{n-1}\). Название связано с тем, что отрезок от позиции \(i\) до конца массива является суффиксом.

Как построить

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

\[s_{n-1}=a_{n-1},\qquad s_i=a_i+s_{i+1}\quad (i=n-2,n-3,\dots,0)\]

После построения сумма хвостового отрезка \(a_i,a_{i+1},\dots,a_{n-1}\) равна \(s_i\) и находится за \(O(1)\). Само построение занимает \(O(n)\) времени и \(O(n)\) дополнительной памяти, если хранить отдельный массив.

№

Пример

Пусть \(a=[3,1,4,2]\). Справа налево получаем: \(s_3=2\), \(s_2=4+2=6\), \(s_1=1+6=7\), \(s_0=3+7=10\). Значит, сумма элементов с индекса \(1\) до конца равна \(s_1=7\).

Не путайте с префиксными суммами

Префиксная сумма относится к началу массива: от первого элемента до выбранной позиции. Суффиксная сумма относится к концу: от выбранной позиции до последнего элемента. Для произвольного отрезка чаще применяют префиксные суммы или приёмы обработки отрезка массива.

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

Для массива \([5, -2, 3, 1]\) чему равна суффиксная сумма с индексом \(1\)?

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

Главное

Суффиксная сумма \(s_i\) — сумма элементов от позиции \(i\) до конца массива.
Суффиксные суммы строят справа налево по правилу \(s_i=a_i+s_{i+1}\).
Сумма любого хвостового отрезка после построения находится за \(O(1)\), а построение занимает \(O(n)\).