Выбор ответа Junior Префиксные суммы спрашивают часто обновлено
Сумма на отрезке
Вопрос
Массив не меняется, приходит q запросов «сумма от i до j включительно». Как отвечать быстрее всего?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Префиксный массив за O(n), ответ pre[j + 1] - pre[i]. Префиксные суммы: pre[k] это сумма первых k элементов.
Варианты ответа
- Префиксный массив за O(n), ответ
pre[j + 1] - pre[i]правильный ответ - Считать сумму циклом на каждый запрос, O(n) на запрос
- Отсортировать массив и искать границы бинпоиском
- Заранее сохранить в Map суммы всех пар (i, j)
Разбор
Префиксные суммы: pre[k] это сумма первых k элементов. Сумма на [i, j] равна pre[j + 1] - pre[i]. Итого O(n + q).
- Цикл на запрос даёт O(n · q).
- Сортировка ломает индексы.
- Все пары это O(n²) памяти и времени на подготовку.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.