Задача №3317. Суммы на подотрезках с изменением элемента
Реализуйте эффективную структуру данных, позволяющую изменять элементы массива и вычислять суммы нескольких подряд идущих элементов.
В первой строке вводится одно натуральное число N (1 ≤ N ≤ 100000) — количество чисел в массиве.
Во второй строке вводятся N чисел от 0 до 100000 — элементы массива.
В третьей строке вводится одно натуральное число M (1 ≤ M ≤ 30000) — количество запросов.
Каждая из следующих M строк представляет собой описание запроса. Сначала вводится одна буква, кодирующая вид запроса (s — вычислить сумму, u — обновить значение элемента).
Следом за s вводятся два числа — номера левой и правой границы отрезка.
Следом за u вводятся два числа — номер элемента и его новое значение.
Для каждого запроса s выведите результат. Все числа выводите в одну строку через пробел.
10 613 263 312 670 216 142 976 355 488 370 10 s 2 7 s 4 8 u 7 969 u 1 558 s 2 7 u 2 731 s 4 9 s 1 3 u 8 76 u 5 377
2579 2359 2572 2840 1601