【例题1】单点修改区间查询

题目描述

给定数列$a_1$,$a_2$,$\ldots$,$a_n$，你需要依次进行$q$个操作，操作有两类：

• $1$ $i$ $x$：给定$i$,$x$，将$a_i$加上$x$；
• $2$ $l$ $r$：给定$l$,$r$，求$\sum_{i=l}^{r}a_i$的值（换言之，求$a_l+a_{l+1}+\cdots+a_r$的值）。

输入格式

第一行包含$2$个正整数$n$,$q$，表示数列长度和询问个数。保证$1 \leq n,q \leq 10^{6}$。

第二行$n$个整数$a_1$,$a_2$,$\ldots$,$a_n$，表示初始数列。保证$|a_i| \leq 10^{6}$。

接下来$q$行，每行一个操作，为以下两种之一：

• $1$ $i$ $x$：给定$i$,$x$，将$a_i$加上$x$；
• $2$ $l$ $r$：给定$l$,$r$，求$\sum_{i=l}^{r}a_i$的值。

保证$1 \leq l \leq r \leq n$，$|x| \leq 10^{6}$。

输出格式

对于每个$2$ $l$ $r$操作输出一行，每行有一个整数，表示所求的结果。

数据范围与提示

对于所有数据，$1 \leq n,q \leq 10^{6}$，$|a_i| \leq 10^{6}$，$1 \leq l \leq r \leq n$，$|x| \leq 10^{6}$。

样例

3 2
1 2 3
1 2 0
2 1 3

6