eolymp
Yarışlar

Дерево Фенвика

Изменение на отрезке High

Задан набор из n целых чисел a0, a1, ..., an-1. Изначально все эти числа равны 0. Далее поступают запросы на изменение и вывод. Для запроса на изменение задаются три числа l, r, d. По этому запросу к каждому из элементов ai (lir) необходимо прибавить значение d. Для запроса на вывод задается одно число i. По этому запросу требуется вывести текущее значение элемента ai.

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

В первой строке задается два целых числа n и m (1n106, 0m106), обозначающих количество элементов и количество запросов соответственно. В последующих m строках задаются запросы. Запрос на изменение задается строкой вида "**A l r d**" (0lr < n, |d| ≤ 103), запрос на вывод - строкой "**Q i**" (0i < n). Все числа целые.

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
10 6
A 3 7 1
Q 4
A 1 5 2
Q 4
Q 1
Q 6
Çıxış verilənləri #1
1
3
2
1
Müəllif Неспирный В.Н.