Выбор ответа Senior Префиксные суммы обновлено
Сумма прямоугольника
Вопрос
Двумерный префикс P[r][c] хранит сумму прямоугольника от (0,0) до (r-1, c-1). Как получить сумму прямоугольника от (r1, c1) до (r2, c2) включительно?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]. Включение-исключение: из большого прямоугольника вычитаем полосу сверху и полосу слева, а угол, вычтенный дважды, возвращаем.
Варианты ответа
P[r2][c2] - P[r1][c1]P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]правильный ответP[r2+1][c2+1] - P[r1][c1]P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1]
Разбор
Включение-исключение: из большого прямоугольника вычитаем полосу сверху и полосу слева, а угол, вычтенный дважды, возвращаем. O(1) на запрос после O(R · C) подготовки.
- Вычитание одного угла не убирает полосы.
- Без индексного сдвига потеряем строку и столбец.
- Без
+ P[r1][c1]угол вычтен дважды.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.