Конвейер и отчёт по первым секциям

На заводе стоит длинный конвейер из n секций, пронумерованных от 1 до n. В каждой секции лежит некоторое число деталей (оно может быть отрицательным — например, если по учёту есть долг).

Диспетчер делает два типа действий:

• иногда он меняет количество деталей в одной секции на некоторую величину (прибавляет или убавляет);
• иногда он просит отчёт: сколько деталей сейчас находится в первых r секциях (от 1 до r).

Твоя задача — быстро отвечать на такие запросы.

Формат ввода

В первой строке заданы два целых числа n и q — количество секций и количество действий. Во второй строке задано n целых чисел a1, a2, ..., an — начальные значения по секциям. Далее идут q строк, каждая описывает одно действие одного из видов:

• ADD i x — прибавить x к значению в секции с номером i.
• SUM r — вывести сумму a1 + a2 + ... + ar по текущему состоянию.

Формат вывода

Для каждого запроса вида SUM r выведи одно целое число в отдельной строке.

Ограничения

• 1 ≤ n ≤ 65000
• 1 ≤ q ≤ 65000
• -1000000 ≤ ai ≤ 1000000
• -1000000 ≤ x ≤ 1000000
• 1 ≤ i ≤ n
• 1 ≤ r ≤ n

Пример

Ввод:

5 6
3 -2 5 0 4
SUM 3
ADD 2 10
SUM 2
ADD 5 -7
SUM 5
SUM 1

Вывод:

6
11
13
3

Если после каждого ADD пересчитывать все обычные префиксные суммы, придётся менять значения от позиции i до n. Это до n действий на один запрос, а при 65000 операциях может быть слишком долго.

Здесь подходит дерево Фенвика (Binary Indexed Tree). Это массив bit, где ячейка с номером i хранит сумму некоторого блока, оканчивающегося в i. Размер блока определяется последним установленным битом числа i:

lowbit(i) = i & -i

Например, bit[6] отвечает за блок из 2 позиций, а bit[8] — за блок из 8 позиций. Благодаря этому любой префикс можно разбить всего на несколько таких блоков.

План решения:

• Создать массив bit размера n + 1: дерево удобно делать с индексацией от 1.
• Начальные значения не хранить отдельно для запросов: для каждого a[i] вызвать операцию добавления add(i, a[i]).
• Для ADD i x идти от i вправо: прибавлять x в bit[i], затем переходить в i + lowbit(i). Так обновляются все блоки, содержащие позицию i.
• Для SUM r идти от r влево: добавлять bit[r] к ответу, затем переходить в r - lowbit(r). Собранные блоки точно покрывают позиции от 1 до исходного r.
• Каждый найденный ответ сохранить или сразу вывести.

Обе операции делают не более O(log n) шагов, поэтому общее время — O((n + q) log n), память — O(n).

Частая ошибка — использовать индексацию с нуля. Формула i & -i и переходы дерева рассчитаны на позиции от 1; индекс 0 в цикле обновления приведёт к бесконечному циклу.