【codevs1082】线段树练习 3

2013年12月28日2,2090

题目描述 Description

给你N个数,有两种操作:
1:给区间[a,b]的所有数增加X
2:询问区间[a,b]的数的和。

输入描述 Input Description

第一行一个正整数n,接下来n行n个整数,

 

再接下来一个正整数Q,每行表示操作的个数,

 

如果第一个数是1,后接3个正整数,

 

表示在区间[a,b]内每个数增加X,如果是2,

 

表示操作2询问区间[a,b]的和是多少。

输出描述 Output Description

对于每个询问输出一行一个答案

样例输入 Sample Input

3

1

2

3

2

1 2 3 2

2 2 3

样例输出 Sample Output

9

数据范围及提示 Data Size & Hint

数据范围

1<=n<=200000

1<=q<=200000

代码

 

貌似我的写法比较奇怪

把一个区间打上标记

这个区间的值都是真实的

而这个区间下面的区间是不真实的

因为下面的区间不一定会询问到所以不用将其变为真实

传递标记就是让一个区间的左右区间的值变得真实

区间标记用于所有针对于区间的修改