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

Секретная корпорация, занимающаяся поиском инопланетных жизненных форм обнаружила на одной из планет созвездия Альфа удивительные живые организмы (даже не плоские, а одномерные). Она приняла решение вести наблюдение за развитием и изменением численности организмов, с этой целью на орбиту планеты был послан спутник - наблюдатель, который мог следить за изменениями численности организмов. Недостаток этого «наблюдателя» в том, что он может отслеживать изменения только на той территории планеты, которая находится непосредственно под ним.

С этой целью его траектория была разбита на равные интервалы. Они пронумерованы от 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 интервал.

Все числа во входных данных не превосходят 10⁵ по абсолютной величине.

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

В выходной файл OUTPUT.TXT для каждого запроса суммы в отдельной строке выведите результат.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]