eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Дима и большой массив

Дима и большой массив

Лимит времени 7 секунд
Лимит использования памяти 256 MiB

Мама подарила мальчику Диме массив длины n. Массив этот не простой, а особенный. Дима может выбрать два числа i и d (1in, -1000d1000), и к элементу с индексом i магически прибавляется d. Дима играет со своим массивом, а мама время от времени задает ему вопросы - какова сумма всех чисел в массиве с индексами от f до t? Однако мама очень занята и не может задавать вопросы так часто, как обычно - всего она задала не более 1000 вопросов. Дима легко справился с этими вопросами, сможете ли Вы?

Входные данные

В первой строке находятся два целых числа n и q (1n10^6, 1q5 ·10^5) - количество элементов в массиве и суммарное количество операций и запросов соответственно. В следующей строке дано n чисел a[1], a[2], ..., a[n] (-1000a[i]1000) - начальное состояние массива. В следующих q строках заданы операции и запросы. Первый символ в строке может быть + или ?. Если строка начинается с +, то это операция прибавления. Далее следуют i и d, ограничения на которые описаны в условии. Если строка начинается с ?, то это запрос. Далее следуют числа f и t (1f, tn).

Выходные данные

Для каждого запроса выведите сумму чисел в массиве с индексами от f до t, по одному результату в строке.

Пример

Входные данные #1
3 3
1 2 3
? 1 3
+ 3 -1
? 1 3
Выходные данные #1
6
5
Автор Егор Куликов
Источник Зимняя Школа Харьков 2012