Дневник дежурного: суммы по отрезкам

В школе ввели «дневник дежурного»: на каждой перемене дежурный записывает число очков в журнал — иногда это похвала (плюс), иногда замечание (минус).

Завуч любит спрашивать: «Сколько всего очков набралось с перемены L по перемену R включительно?» Таких вопросов много, и отвечать нужно быстро.

Важно: итоговые суммы могут не помещаться в 32-битный тип (как на олимпиадах). В Python это не проблема, но в других языках нужен 64-битный тип.

Формат ввода

Первая строка: два целых числа n и q — число перемен и число вопросов.

Вторая строка: n целых чисел a1, a2, ..., an — записи в дневнике.

Далее q строк, в каждой два целых числа L и R (1 ≤ L ≤ R ≤ n) — запрос суммы на отрезке.

Формат вывода

Выведите q строк. В i-й строке — сумму aL + a(L+1) + ... + aR для i-го запроса.

Ограничения

• 1 ≤ n ≤ 20000
• 1 ≤ q ≤ 20000
• -1 000 000 ≤ ai ≤ 1 000 000
• 1 ≤ L ≤ R ≤ n

Пример

Ввод:

5 3
2 -1 3 0 4
1 3
2 5
4 4

Вывод:

4
6
0

Ключевое наблюдение: сумму на отрезке L..R можно получить, если знать «сколько набралось» до R и до L-1. Тогда отрезок — это разница: pref[R] - pref[L-1].

Почему это работает: префиксная сумма pref[i] хранит сумму первых i элементов. Если вычесть сумму первых L-1 элементов, останется ровно то, что лежит между L и R включительно. Это превращает много запросов из «пересчитать каждый раз» в «посмотреть 2 числа и вычесть».

План решения:

• Считай n и q, затем массив a из n чисел.
• Построй массив pref длины n+1: pref[0] = 0.
• Для i от 1 до n: pref[i] = pref[i-1] + a[i] (удобно хранить a с 1-индексацией или аккуратно сдвигать индексы).
• Для каждого запроса (L, R) выведи pref[R] - pref[L-1].

Мини-сниппет формулы ответа: ans = pref[r] - pref[l-1].

Сложность: построение префиксов O(n), каждый запрос O(1), итого O(n + q) по времени и O(n) по памяти.

Частая ошибка: перепутать индексацию (0/1) и сделать pref[L] вместо pref[L-1]. Поэтому pref делают длины n+1 и явно задают pref[0]=0 — так граница L=1 обрабатывается без условий.