P048 线段树（区间求和）

题目描述

维护一个长度为 n 的数组，支持以下操作：

- update i x：将 a[i] 加上 x
- query l r：查询 a[l] + a[l+1] + \dots + a[r]

输入格式

第一行两个整数 n, q（1 \le n, q \le 10^5）。
第二行 n 个整数，表示初始数组。
接下来 q 行，每行一个操作。

输出格式

对每个 query 操作输出一行。

样例

输入:
5 4
1 2 3 4 5
query 1 3
update 2 3
query 1 3
query 2 4

输出:
6
9
12