3311. [模板]可持久化线段树1

【题目描述】

给定一个长度为$n$的整数序列$a$，为第$0$版，然后执行$m$次操作：

0 x y，表示产生一个新版本，然后将$a[x]$增加$y$。

1 k l r，表示查询第$k$个版本中$a[l,r]$的和。

【输入格式】

第一行一个正整数$n$，表示序列$a$的大小，一个正整数$m$，表示$m$次操作。

第二行包含$n$个整数，表示序列$a$。

接下来$m$行，每行一个操作，具体格式参考【题目描述】。

【输出格式】

对于每个查询操作，输出一行一个整数表示答案。

【样例输入】

5 8
4 3 6 2 4
0 2 1
0 5 7
1 2 1 4
0 3 4
1 1 2 4
1 3 4 4
0 4 6
1 4 2 4

【样例输出】

16
12
2
22

【数据规模与约定】

$1\leq n, m\leq 10^5,|a[i|,|y|\leq 10^9$，保证$1\leq k\leq $已经存在的版本。