【模板】线段树1
题号:NC226533
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

给你一个长度为n的整数序列a_1, a_2, ...a_n,和q次操作,每次操作可能进行如下动作:

1. 选择一个数a_i,将其加上k。
2. 选择一个区间[l,r], 求a_l, ... , a_r的和。

输入描述:

第一行输入两个整数n和q,表示数组长度和操作次数。
第二行输入 n 个数字,代表数组 a 。
接下来q行,每行的第一个整数op表示动作类型
若op=1, 则后面有两个参数i和k,表示把a_i加上k。
若op=2,则后面有两个参数l和r,表示求a_l, ... , a_r的和。



1 \leq op \leq 2
1 \leq l \leq r \leq n

输出描述:

对每次op=2的操作,请输出一行表示和值。
示例1

输入

复制
5 5
1 2 3 4 5
1 1 5
2 2 4
1 4 -2
1 5 5
2 1 5

输出

复制
9
23