e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

ADA University - January 13 - Segment Tree

Діма та масив

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

Вхідні дані

У першому рядку знаходиться два цілих числа n та q (1n5 * 105, 1q105) - кількість елементів у масиві і сумарна кількість операцій та запитів відповідно. У наступному рядку задано n чисел a1, a2, ..., an (-1000ai1000) - початковий стан масиву. У наступних q рядках задані операції та запити. Перший символ у рядку може бути = або ?. Якщо рядок починається з =, то це операція присвоювання. Далі йдуть i та d, обмеження на які описано в умові. Якщо рядок починається з ?, то це запит. Далі йдуть числа f і t (1f, tn).

Вихідні дані

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
3 3
1 2 3
? 1 3
= 3 2
? 1 3
Вихідні дані #1
6
5
Автор Єгор Куліков
Джерело Зимова Школа Харків 2012