数列操作与求和模板题

一、题目描述

给定一个数列$a_1, a_2, \cdots, a_n$，需要依次执行$q$个操作，操作分为以下两类：

• 操作类型1：格式为“$1\ i\ x$”，即给定下标$i$和数值$x$，将数列中的元素$a_i$加上$x$。
• 操作类型2：格式为“$2\ l\ r$”，即给定区间左右端点$l$和$r$，计算并输出数列中从$a_l$到$a_r$这些元素的和，也就是$\sum_{i = l}^{r} a_i$的值。

二、输入格式

• 第一行：包含两个正整数$n$和$q$，分别表示数列的长度和操作的个数，保证$1 \leq n, q \leq 10^6$。
• 第二行：包含$n$个整数$a_1, a_2, \cdots, a_n$，表示初始的数列，保证每个元素的绝对值$\vert a_i \vert \leq 10^6$。
• 接下来$q$行：每行代表一个操作，格式为“$1\ i\ x$”或“$2\ l\ r$”，保证$1 \leq l \leq r \leq n$，$\vert x \vert \leq 10^6$ 。

三、输出格式

对于每一个类型为“$2\ 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$ 。