P100 树状数组（单点修改区间求和）

题目描述

给定 n 个整数 a1, \dots, an，处理 q 个操作：

- 1 i v：将 ai 增加 v
- 2 l r：查询 \sum{i=l}^{r} ai

要求：每个操作 O(\log n)。

输入格式

第一行 n, q（1 \le n, q \le 10^5）。
第二行 n 个整数 ai（|ai| \le 10^9）。
接下来 q 行，每行一个操作。
（修改时 |v| \le 10^9）

输出格式

对每个查询操作，输出一行结果。

样例

输入:
5 4
1 2 3 4 5
2 1 5
1 3 10
2 1 5
2 2 4

输出:
15
25
9