题目描述

东东有一个长度为 $n$ 的整数序列 $a_1,a_2,\dots,a_n$，他希望实现以下两种操作：

• 将某个位置 $x$ 的值修改为 $y$；
• 查询区间 $[x,y]$ 内所有数的和。

请你帮他实现这个功能。

输入格式

第一行两个整数 $n,q$，表示序列长度和操作次数。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示初始序列。

接下来 $q$ 行，每行三个整数，表示一个操作：

• 若第一个整数为 1，表示将 $a_x$ 修改为 $y$；
• 若第一个整数为 2，表示查询区间 $[x,y]$ 的元素和。

输出格式

对于每个查询操作，输出一行一个整数，表示该次查询的结果。

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

6
14
7

数据规模与约定

• 第一次查询 $a_1 + a_2 + a_3 = 1 + 2 + 3 = 6$；

• 第二次将 $a_2$ 修改为 $10$；

• 再次查询 $a_1 + a_2 + a_3 = 1 + 10 + 3 = 14$；

• 第三次将 $a_5$ 修改为 $0$；

• 最后查询 $a_3 + a_4 + a_5 = 3 + 4 + 0 = 7$。

• 对于 $100\%$ 的数据，$1 \le n,q \le 10^5$，$-10^9 \le a_i,y \le 10^9$，$1 \le x \le n$，保证查询区间合法。