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

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

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

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

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

Формат ввода

В первой строке задано целое число t — количество наборов данных. Далее идут t наборов данных.

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

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

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

Для каждого набора выведи ответы на все запросы вида SUM r в том порядке, в котором они встречаются во входных данных. Каждый ответ выведи в отдельной строке.

Ограничения

• 1 ≤ t ≤ 4
• 1 ≤ n ≤ 65000
• 1 ≤ q ≤ 65000
• Сумма значений n по всем наборам не превышает 65000.
• Сумма значений q по всем наборам не превышает 65000.
• -1000000 ≤ ai ≤ 1000000
• -1000000 ≤ x ≤ 1000000
• 1 ≤ i ≤ n
• 1 ≤ r ≤ n

Пример

Ввод:

3
1 1
0
SUM 1
1 3
-1000000
ADD 1 1000000
SUM 1
SUM 1
5 4
1 2 3 4 5
SUM 5
ADD 5 -10
SUM 5
SUM 1

Вывод:

0
0
0
15
5
1

Если после каждого 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 в цикле обновления приведёт к бесконечному циклу.