数列操作与求和问题

题目描述

这是一道模板题。给定一个数列 $a_1, a_2, \dots, a_n$，需要依次执行 $q$ 个操作，操作分为以下两类：

1. 更新操作：操作格式为“1 i x”，表示将数列中第 $i$ 项 $a_i$ 的值增加 $x$ 。
2. 查询操作：操作格式为“2 l r”，要求计算并输出数列中从第 $l$ 项到第 $r$ 项的和，即$\sum_{i = l}^r a_i = a_l + a_{l + 1} + \cdots + a_r$的值。

输入格式

1. 第一行包含两个正整数 $n$ 和 $q$，分别表示数列的长度和操作的个数。其中，$1\leq n,q\leq 10^6$。
2. 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，用于描述初始数列，且满足$\vert a_i\vert\leq 10^6$。
3. 接下来的 $q$ 行，每行描述一个操作，格式为“1 i x” 或 “2 l r”。其中，对于“1 i x”操作，$\vert x\vert\leq 10^6$；对于“2 l r”操作，$1\leq l\leq r\leq n$。

输出格式

对于每个“2 l r”的查询操作，输出一行，该行包含一个整数，表示从第 $l$ 项到第 $r$ 项的和。

样例

样例输入

3 2
1 2 3
1 2 0
2 1 3

样例输出

6

数据范围与提示

对于所有数据，满足$1\leq n,q\leq 10^6$，$\vert a_i\vert\leq 10^6$，$1\leq l\leq r\leq n$，$\vert x\vert\leq 10^6$。