Запросы на сумму в диапазоне (Range Sum Queries) 2
Вам дан массив из
n элементов и q запросов. Существует два типа запросов:- Получить сумму элементов на указанном отрезке
- Обновить элемент массива в заданной позиции
Ваша задача — эффективно обработать эти запросы.
Входные данные
Первая строка содержит два целых числа
n и q (1 ≤ n, q ≤ 100 000), которые обозначают количество элементов в массиве и количество запросов соответственно.Вторая строка содержит
n целых чисел, разделенных пробелами, (), являющихся начальными элементами массива.Каждая из следующих
q строк описывает один запрос:- Для запросов на сумму по диапазону: строка начинается с числа
1, за которым следуют два целых числа и (). Эти числа задают границы[ $$l_i, r_i$$ ], по которым нужно вычислить сумму элементов.
- Для запросов на обновление массива: строка начинается с числа
2, за которым идут два целых числа и (), указывающих индекс элемента, который нужно обновить, и его новое значение .
Выходные данные
Для каждого запроса на сумму по диапазону выведите сумму элементов в заданных границах в отдельной строке.
Примеры
Входные данные | Выходные данные |
5 3
1 2 3 4 5
1 1 3
1 2 4
1 1 5 | 6
9
15 |
5 3
1 2 3 4 5
1 1 3
2 1 5
1 1 5 | 6
19 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB