Чередующаяся сумма
Вам дан массив из
n целых чисел и q запросов. Существует два вида запросов: обновление элемента массива по индексу p и вычисление чередующейся суммы подмассива [l; r].Чередующаяся сумма подмассива
[l; r] определяется как сумма элементов на четных индексах минус сумма элементов на нечетных индексах внутри подмассива. Другими словами, если подмассив [l; r] содержит элементы , тогда чередующаяся сумма задается формулой .Для каждого запроса типа 2 требуется вычислить и вывести чередующуюся сумму указанного подмассива
[l; r].Входные данные
Первая строка содержит два числа
n и q, задающие размер массива и количество запросов соответственно (1 ≤ n, q ≤ ).
Вторая строка содержит n целых чисел (где ), описывающих элементы массива.
Каждая из следующих q строк соответствует одному запросу и может иметь формат: 1 l r или 2 p x. Здесь 1 означает запрос на вычисление чередующейся суммы подмассива [l; r], а 2 указывает на обновление массива в позиции p значением x (где 1 ≤ p ≤ n, 1 ≤ x ≤ , 1 ≤ l ≤ r ≤ n).Выходные данные
Для каждого запроса типа 2 выведите вычисленную чередующуюся сумму подмассива в отдельной строке.
Примеры
Входные данные | Выходные данные |
8 3
1 2 3 4 5 6 7 8
1 2 6
2 4 9
1 1 8 | 4
-9 |
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB