Дерево Фенвика
(Время: 1 сек. Память: 16 Мб Сложность: 45%)
Секретная корпорация, занимающаяся поиском инопланетных жизненных форм обнаружила на одной из планет созвездия Альфа удивительные живые организмы (даже не плоские, а одномерные). Она приняла решение вести наблюдение за развитием и изменением численности организмов, с этой целью на орбиту планеты был послан спутник - наблюдатель, который мог следить за изменениями численности организмов. Недостаток этого «наблюдателя» в том, что он может отслеживать изменения только на той территории планеты, которая находится непосредственно под ним.
С этой целью его траектория была разбита на равные интервалы. Они пронумерованы от 1 до N. По запросу с Земли о количестве живых форм в интервале с L по R (L ≤ R) - спутник должен, пролетая над ними (L, L+1, …,R-1, R интервалами) произвести подсчет и затем, в ответ на запрос, отправить полученные данные. Но количество организмов постоянно изменяется: в некоторое время в X интервале на Y единиц.
Помогите написать программу для спутника, которая будет отвечать на запросы и отслеживать количество единиц жизни в каждом интервале.
Входные данные
Первая строка входного файла INPUT.TXT содержит два натуральных числа N и M – количество интервалов и запросов соответственно. В последующих M строках расположены запросы в следующем формате:
add X Y – изменение числа организмов в интервале с номером X на Y единиц;
rsq L R – запрос суммарного количества организмов с L по R интервал.
Все числа во входных данных не превосходят 105 по абсолютной величине.
Выходные данные
В выходной файл OUTPUT.TXT для каждого запроса суммы в отдельной строке выведите результат.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 2 3
add 1 4
rsq 1 1
rsq 1 1 | 4 4 |
2 | 4 8
rsq 1 4
add 1 3
add 4 2
rsq 2 4
rsq 1 2
add 4 -2
add 2 8
rsq 1 4 | 0
2
3
11 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|