学生成绩修改系统

题目描述

学校共有 n 名学生，编号为：

1 ~ n

第 i 名学生当前成绩为：

a[i]

教务系统需要实时维护学生成绩。

系统支持两种操作：

---

操作类型 1：修改成绩

输入：

0 p x

表示：

将第 p 名学生的成绩修改为 x。

即： $a_p=x$

注意：

此操作不是增加成绩！

例如：

原成绩：

80

执行：

0 3 100

表示：

a[3]=100

不是：

80+100

---

操作类型 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
10 20 30 40 50
1 1 5
0 3 100
1 1 5
0 5 5
1 3 5

---

输出样例

150
220
145

---

样例解释

初始成绩：

编号：
1  2  3  4  5

成绩：
10 20 30 40 50

---

第一次操作

1 1 5

查询所有学生：

10+20+30+40+50=150

输出：

150

---

第二次操作

0 3 100

表示：

第 3 名学生成绩修改为：

100

成绩变为：

10 20 100 40 50

---

第三次操作

1 1 5

查询：

10+20+100+40+50=220

输出：

220

---

第四次操作

0 5 5

第 5 名学生：

原来：

50

修改为：

5

成绩：

10 20 100 40 5

---

第五次操作

1 3 5

查询：

100+40+5=145

输出：

145

测试点编号	n ≤	q ≤	难度层级	特殊性质	设计目的
1		5	弱数据	单元素、多次修改	覆盖最小规模、单点查询、正负修改
2	5	8		小数组、普通区间	检查基础建树、区间查询、首尾修改
3	6	10	正常数据	全相同、重复修改同一位置	覆盖修改为相同值、反复覆盖旧值
4	8			全负数、局部查询	检查负数区间和、负数改正数
5	16	11		2 的幂规模、边界位置	覆盖树状数组低位边界、首尾和中间点修改
6	5	9		long long 大数	防止使用 int 导致溢出
7	20	13		正负混合、多段查询	覆盖较复杂的修改后连续查询
8	10	25		初始全 0、操作密集	检查多次增减、清零、局部区间变化
9	500000	11	极限数据	n 达数组上界、稀疏修改	覆盖最大 n、首尾与中点位置
10	1000	200		随机压力、修改查询混合	检查较多操作下的动态维护正确性