分段台账单点增加

难度：T4

【知识点：线段树基础】

前置知识：线段树基础及其冻结前置单元。

题目描述与输入

输入$n$、$q$及$n$个整数。操作$1$ $x$ $y$表示把位置$x$增加$y$；操作$2$ $l$ $r$查询闭区间和。

输出

每问输出区间和。

数据范围

$1$<=$n,q<=2000$；更新下标在$1$..$n$；$1$<=$l<=r<=n$；初值及更新数绝对值<=$10^6$。

样例输入

4 4
1 2 3 4
2 1 4
1 2 5
2 1 2
2 2 4

样例输出

10
8
14

样例说明

先辨认增加与赋值的区别，必要时保存原值计算增量。请按输入操作顺序逐步核对；没有规定输出的更新操作不输出额外内容。