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

Знакочередование

Знакочередование

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

Реализуйте структуру данных из n элементов a[1], a[2], ..., a[n], поддерживающую следующие операции:

  • присвоить элементу a[i] значение j;

  • найти знакочередующуюся сумму на отрезке от l до r включительно, т.е. (a[l] - a[l+1] + a[l+2] - ... a[r]).

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

В первой строке содержится натуральное число n (1n10^5) - длина массива. Во второй строке записаны начальные значения элементов - неотрицательные целые числа, не превосходящие 10^4.

В третьей строке находится натуральное число m (1m10^5) - количество операций. В последующих m строках записаны операции:

  • операция первого типа задаётся тремя числами 0 i j (1in, 1j10^4);

  • операция второго типа задаётся тремя числами 1 l r (1lrn).

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

Для каждой операции второго типа выведите в отдельной строке соответствующую знакочередующуюся сумму.

Пример

Входные данные #1
3
1 2 3
5
1 1 2
1 1 3
1 2 3
0 2 1
1 1 3
Выходные данные #1
-1
2
-1
3