#Pbit14. 【例题4】区间修改区间查询

    ID: 183 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 普及+/提高- 上传者: 标签>树状数组赛制:OI来源:wyfoj http://127.0.0.1

【例题4】区间修改区间查询

【例题4】区间修改区间查询

题目描述

这是一道模板题。这是一道模板题。

给定数列a[1],a[2],...a[n],你需要依次进行q个操作,操作有两类:给定数列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。第一行包含2个正整数n,q,表示数列长度和询问个数。保证1<=n,q<=10^6。 第二行n个整数a[1],a[2],...a[n],表示初始数列。保证∣a[i]∣<=106。第二行n个整数a[1],a[2],...a[n],表示初始数列。保证|a[i]|<=10^6。 接下来q行,每行一个操作,为以下两种之一:接下来q行,每行一个操作,为以下两种之一:

1 l r x:对于所有i∈[l,r],将a[i]加上x;对于所有i\in [l,r],将a[i]加上x;

2 l r:输出∑i=lra[i]的值。输出\sum_{i=l}^r a[i]的值。

保证1<=l<=r<=n,∣x∣<=106。保证1<=l<=r<=n,|x|<=10^6。

输出格式

对于每个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。$