Вопрос 7 из 23

Практика: структуры данных

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

От чтения к действию

А теперь — вы

Для массива [3,5,−2,8] построено P=[0,3,8,6,14]. Чему равна сумма полуинтервала [1,3)?

Разберёмся в теме

Префиксная сумма P(k) хранит сумму первых k элементов, причём P(0)=0. Сумма элементов с индексами от l включительно до r исключительно равна P(r)−P(l). После подготовки массива каждый такой запрос требует двух чтений и одного вычитания.

Объяснение и примеры

Частые вопросы

Где найти подробное решение?

Перейдите по ссылке «Объяснение и примеры» над этим блоком. Там разобрана тема текущего вопроса.

Можно ли попробовать снова?

Да. После проверки можно изменить ответ. Переход к следующему вопросу не блокируется результатом, а личный счёт не сохраняется.