305 - 线段树之区间更新

通过次数

21

提交次数

56

时间限制 : 2 秒
内存限制 : 256 MB

已知有N个整数,A1,A2,...,AN。

你需要处理两种操作。 一种操作是在给定区间中为每个数字添加一个给定数字。 另一种是要求给定间隔中的数字总和。

输入

第一行包含两个数字N和Q.1≤N,Q≤100000。

第二行包含N个数字,A1,A2,...,AN的初始值。 -1000000000≤AI≤1000000000。

接下来的Q行中的每一行代表一个操作。

“C a b c”表示将c添加到Aa,Aa + 1,...,Ab中的每一个。 -10000≤c≤10000。

“Q a b”表示查询Aa,Aa + 1,...,Ab的总和。

输出

对于Q询问操作,你需要输出一行,表示答案。

样例

输入

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

输出

4
55
9
15