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

ADA University - January 13 - Segment Tree

Сума на відрізку

Задано масив з n чисел. Знайдіть суму чисел на відрізку.

Вхідні дані

Перший рядок містить два цілих числа n та k - кількість чисел в масиві та кількість запитів (1n105, 0k105). Наступні k рядків містять запити двох типів:

  • A i x - присвоїти i-му елементу масива значення x(1in, 0x109);
  • Q l r - знайти суму чисел в масиві на позиціях від l до r (1lrn).

Спочатку в масиві знаходяться нулі.

Вихідні дані

На кожен запит виду Q l r вивести суму чисел на відрізку [l; r].

Ліміт часу 1 секунд
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
5 9
A 2 2
A 3 1
A 4 2
Q 1 1
Q 2 2
Q 3 3
Q 4 4
Q 5 5
Q 1 5
Вихідні дані #1
0
2
1
2
0
5