2316: 树状数组模板
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：10
解决：6
题目描述
已知一个数列，你需要进行下面两种操作：
1.将某一个数加上x
2.求出某区间每一个数的和
1.将某一个数加上x
2.求出某区间每一个数的和
输入
第一行包含两个正整数n，m。分别表示该数列数字的个数和操作的总个数。
第二行包含n个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。
接下来m行每行包含3个整数，表示一个操作，具体如下：
1 x k 含义：将第x个数加上k
2 x y 含义：输出区间[x,y]内每个数的和
第二行包含n个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。
接下来m行每行包含3个整数，表示一个操作，具体如下：
1 x k 含义：将第x个数加上k
2 x y 含义：输出区间[x,y]内每个数的和
输出
输出包含若干行整数，即为所有操作2的结果。
样例输入 复制
5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4样例输出 复制
14
16提示
数据范围：
对于30%的数据，1≤ n ≤ 8，1≤ m ≤ 10；
对于70%的数据，1≤ n,m ≤104；
对于100%的数据，1≤ n,m ≤ 5 x 105；
对于30%的数据，1≤ n ≤ 8，1≤ m ≤ 10；
对于70%的数据，1≤ n,m ≤104；
对于100%的数据，1≤ n,m ≤ 5 x 105；