1455: 树状数组3-区间修改,区间查询

Memory Limit:128 MB Time Limit:2.000 S
Judge Style:Text Compare Creator:
Submit:16 Solved:7

Description

给定一个有n个数的数列,m种操作,规定有两种操作,一是修改区间[l,r]的元素值增加一个值x,二是求子数列[l,r]的连续和。

Input

第一行2个整数n,m(n表示输入n个数,m表示m个操作)
第二行n个整数,a1,a2,......,an, |ai|<=106
接下来m行,每行一个操作,为下面两种之1:
1 l r x 表示区间[l,r] 每个元素值加x
2 l r 表示求子数列[l,r]的连续和

Output

若干行,表示k=2时,对应子数列[l,r]连续和。

Sample Input Copy

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

Sample Output Copy

15
34
32
33
50

HINT

所有数据,1<=n,m<=106, |ai|<=106,1<=l<=r<=n,|x|<=106