Карточка Junior Префиксные суммы спрашивают часто обновлено
Префиксная сумма
Вопрос
Что такое префиксная сумма и формула суммы на отрезке?
Попробуйте сами
Ответьте про себя или вслух, потом откройте ответ и сверьтесь.
Показать ответ и разбор
Коротко
Массив pre, где pre[0] = 0, pre[k] = a[0] + ... + a[k-1]. Сумма на [i, j] включительно: pre[j + 1] - pre[i].
Ответ
Массив pre, где pre[0] = 0, pre[k] = a[0] + ... + a[k-1]. Сумма на [i, j] включительно: pre[j + 1] - pre[i]. Строится за O(n), запрос за O(1).
Разбор
Массив pre, где pre[0] = 0, pre[k] = a[0] + ... + a[k-1]. Сумма на [i, j] включительно: pre[j + 1] - pre[i]. Строится за O(n), запрос за O(1).
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.