Городские фонари: сколько света на проспекте?

В городе на одной длинной улице стоят фонари, пронумерованные слева направо от 1 до N. У каждого фонаря есть текущая «яркость» (целое число). Диспетчерская получает команды двух типов:

• поменять яркость одного фонаря;
• узнать, сколько суммарного света дают фонари на отрезке улицы.

Нужно быстро обрабатывать все команды.

Формат ввода

Первая строка: целое число N — количество фонарей. Вторая строка: N целых чисел a1, a2, ..., aN — начальные яркости. Третья строка: целое число Q — количество команд. Далее идут Q строк, каждая — одна команда:

• SET i x — присвоить фонарю с номером i яркость x.
• SUM l r — вывести сумму яркостей фонарей с номерами от l до r включительно.

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

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

Ограничения

• 1 ≤ N ≤ 65000
• 1 ≤ Q ≤ 65000
• 0 ≤ ai ≤ 1000000
• 0 ≤ x ≤ 1000000
• 1 ≤ i ≤ N
• 1 ≤ l ≤ r ≤ N

Пример

Ввод:

5
1 2 3 4 5
6
SUM 2 4
SET 3 10
SUM 1 3
SUM 3 3
SET 5 0
SUM 4 5

Вывод:

9
13
10
4

Главная трудность в том, что после SET обычные префиксные суммы перестают быть удобными: изменение одного фонаря пришлось бы распространять на все следующие суммы. Пересчитывать их каждый раз — долго.

Подходит дерево Фенвика: массив fen, где каждая ячейка хранит сумму небольшого блока. Размер блока определяется младшим установленным битом номера: i & -i. Благодаря этому и изменение, и поиск суммы префикса проходят только по O(log N) ячейкам.

Сумма на отрезке выражается через две префиксные суммы:

sum(l..r) = pref(r) - pref(l - 1)

• Создайте массив текущих яркостей a, чтобы помнить старое значение каждого фонаря.
• Постройте дерево Фенвика: добавьте в него яркость каждого фонаря.
• Для SUM l r найдите pref(r) и вычтите pref(l - 1).
• Для SET i x не заменяйте значение в дереве напрямую. Сначала вычислите изменение: delta = x - a[i].
• Прибавьте delta в дерево Фенвика по позиции i, затем обновите a[i] = x.

Префиксная сумма в дереве находится движением влево: после добавления fen[i] переходите к i -= i & -i. При обновлении, наоборот, двигайтесь вправо: i += i & -i.

Сложность: построение простым добавлением — O(N log N), каждая команда — O(log N). Память — O(N).

Частая ошибка: при SET добавить в дерево x, а не разницу x - a[i]. Тогда старое значение останется в суммах, и ответы станут завышенными.