【例题4】区间修改区间查询
题目描述
这是一道模板题。
给定数列a[1],a[2],...a[n],你需要依次进行q个操作,操作有两类:
1 l r x:$给定l,r,x,对于所有i\in [l,r],将a[i]加上x(换言之,将a[l],a[l+1],...,a[r]分别加上x);$
2 l r:$给定l,r,求的值\sum_{i=l}^r a[i](换言之,求a[l],a[l+1],...a[r]的值)。$
输入格式
第一行包含2个正整数n,q,表示数列长度和询问个数。保证1<=n,q<=106。
第二行n个整数a[1],a[2],...a[n],表示初始数列。保证∣a[i]∣<=106。
接下来q行,每行一个操作,为以下两种之一:
1 l r x:对于所有i∈[l,r],将a[i]加上x;
2 l r:输出∑i=lra[i]的值。
保证1<=l<=r<=n,∣x∣<=106。
输出格式
对于每个2 l r操作,输出一行,每行有一个整数,表示所求的结果。
数据范围
(原站未提供,导入后需人工补齐)
样例
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
15
34
32
33
50
提示
$对于所有数据,1<=n,q<=10^6,|a[i]|<=10^6,1<=l<=r<=n,|x|<=10^6。$