在线查询比赛积分

题目描述

某场比赛共有 n 名选手，编号为：

1 ~ n

第 i 名选手当前积分为：

a[i]

比赛过程中，选手积分会不断变化，系统需要实时维护所有选手的积分信息。

现在有 q 次操作，每次操作有两种类型：

---

操作类型 1：积分增加

输入：

0 p x

表示：

第 p 名选手获得 x 分。

即：

$a_p=a_p+x$

修改完成后，需要保存新的积分。

---

操作类型 2：区间查询

输入：

1 l r

表示查询编号从 l 到 r 的所有选手积分总和：

$a_l+a_{l+1}+...+a_r$

并输出查询结果。

---

请你编写程序，帮助比赛系统完成所有实时积分统计。

---

输入格式

第一行包含两个整数：

n q

表示：

• n：选手数量
• q：操作次数

第二行包含 n 个整数：

a1 a2 ... an

表示初始积分。

接下来 q 行，每行一个操作：

若操作为：

0 p x

表示第 p 名选手增加 x 分。

若操作为：

1 l r

表示查询区间 [l,r] 的积分总和。

---

输出格式

对于每一次查询操作：

1 l r

输出一行答案。

---

数据范围

对于所有测试数据：

1 ≤ n,q ≤ 500000

0 ≤ a[i],x ≤ 10^9

1 ≤ p,l,r ≤ n

保证：

l ≤ r

所有答案均在 long long 范围内。

---

输入样例

5 5
1 2 3 4 5
1 1 5
1 2 4
0 3 10
1 1 5
1 3 3

---

输出样例

15
9
25
13

---

样例解释

初始积分：

编号： 1  2  3  4  5

积分： 1  2  3  4  5

---

第一次操作：

1 1 5

查询所有选手积分：

1+2+3+4+5=15

输出：

15

---

第二次操作：

1 2 4

查询：

2+3+4=9

输出：

9

---

第三次操作：

0 3 10

第 3 名选手增加 10 分。

积分变化：

1 2 13 4 5

---

第四次操作：

1 1 5

查询：

1+2+13+4+5=25

输出：

25

---

第五次操作：

1 3 3

查询第 3 名选手：

13

输出：

13