Сколько выпало дождя
Дан ряд суточных осадков за n дней. Метеорологу нужно ответить на q вопросов вида «сколько выпало с дня l по день r включительно». Вопросов много, периоды бывают длинными — десятки лет.
Второй и третий тесты — осадки Алматы по дням за 1941–2025 годы (реанализ ERA5 через Open-Meteo), в десятых долях миллиметра.
Вход
В первой строке n (1 ≤ n ≤ 2·10⁵), во второй — n целых чисел от 0 до 10⁶. Затем q (1 ≤ q ≤ 10⁵) и q строк с числами l и r (1 ≤ l ≤ r ≤ n).
Выход
Для каждого вопроса — сумма чисел с l-го по r-е.
Примеры
Пример 1
8 0 12 0 35 7 0 0 120 5 1 8 2 2 4 5 6 7 1 1
174 12 42 0 0
Ограничения
- Время · Python
- 3000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 6 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Если каждый вопрос складывает свои дни заново, то при 10⁵ вопросах по 2·10⁵ дней это 2·10¹⁰ сложений. Что можно посчитать один раз заранее, чтобы потом отвечать быстро?
2Идея
Посчитаем P[i] — сумму первых i дней, P[0] = 0. Тогда сумма с l-го по r-й день — это P[r] − P[l − 1]: из суммы первых r дней вычитаем всё, что было до l-го.
3Разбор
Один проход строит P, и каждый вопрос — одно вычитание. Удобно, что массив на единицу длиннее исходного: тогда формула работает и для l = 1 без отдельного случая.
Суммы большие: 2·10⁵ дней по 10⁶ — это 2·10¹¹, в 32-битное целое не помещается. В Go берём int64.
3+Решение
4Сложность
O(n) на построение и O(1) на вопрос, всего O(n + q). Память — O(n).
5Типичные ошибки
- Складывать каждый период заново. Верно, но третий тест — 10⁵ вопросов про периоды по семьдесят-восемьдесят лет, это почти 3·10⁹ сложений.
- Сдвиг на единицу. Дни в условии нумеруются с единицы, а P[i] — сумма первых i. Проверьте на первом примере вопрос «2 2».
- Переполнение. В пятом тесте сумма 5·10¹⁰.