Выбор ответа Senior Префиксные суммы обновлено
Массив разностей
Вопрос
Нужно q раз прибавить v ко всем элементам на отрезке [l, r], а в конце вывести массив. Какой приём даст O(n + q)?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: d[l] += v, d[r + 1] -= v, затем префиксная сумма. Массив разностей обратен префиксной сумме: отметка в начале и снятие после конца, а итоговые значения восстанавливает один проход префиксной суммы.
Варианты ответа
- Цикл по отрезку
[l, r]на каждый запрос, это оптимально - Сортировка запросов по l и слияние отрезков в один
d[l] += v,d[r + 1] -= v, затем префиксная суммаправильный ответ- Map по каждому индексу с суммой прибавок
Разбор
Массив разностей обратен префиксной сумме: отметка в начале и снятие после конца, а итоговые значения восстанавливает один проход префиксной суммы. O(1) на запрос, O(n) в конце.
- Цикл по отрезку O(n · q).
- Сортировка сама по себе ничего не ускоряет.
- Map по индексам сводится к тому же циклу.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.