数据结构--线段树--lazy延迟操作

A Simple Problem with Integers

Time Limit: 5000MS		Memory Limit: 131072K
Total Submissions: 53749		Accepted: 16131
Case Time Limit: 2000MS

Description

You have N integers, A₁, A₂, ... , A_N. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

Input

The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A₁, A₂, ... , A_N. -1000000000 ≤ A_i ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of A_a, A_a₊₁, ... , A_b. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of A_a, A_a₊₁, ... , A_b.

Output

You need to answer all Q commands in order. One answer in a line.

Sample Input

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

Sample Output

//更新某一段区域的时候，采用延迟标记~~
代码：

 1 #include "cstdio" //poj 3468 lazy操作
 2 #include "cstring"
 3 #include "iostream"
 4 using namespace std;
 5 
 6 #define N 100005
 7 #define LL long long
 8 
 9 struct node{
10     int x,y;
11     LL sum;
12     LL add;   //记录以当前节点为根节点的树中需要增加的值
13 }a[3*N];
14 
15 void Build(int t,int x,int y)
16 {
17     a[t].x = x; 
18     a[t].y = y;
19     a[t].sum = a[t].add = 0;
20     if(a[t].x == a[t].y)  //到了叶子节点
21     {
22         scanf("%lld",&a[t].sum);
23         return ;
24     }
25     int mid = (a[t].x + a[t].y)/2;
26     Build(t<<1,x,mid);
27     Build(t<<1|1,mid+1,y);
28     a[t].sum = a[t<<1].sum + a[t<<1|1].sum;
29 }
30 
31 void Push_down(int t)  //将add(增值)向下推一级
32 {
33     LL add = a[t].add;
34     a[t<<1].add += add;
35     a[t<<1|1].add += add;
36     a[t<<1].sum += add*(a[t<<1].y-a[t<<1].x+1);
37     a[t<<1|1].sum += add*(a[t<<1|1].y-a[t<<1|1].x+1);
38     a[t].add = 0;
39 }
40 
41 LL Query(int t,int x,int y)
42 {
43     if(a[t].x==x &&a[t].y==y)
44         return a[t].sum;
45     Push_down(t);
46     int mid = (a[t].x + a[t].y)/2;
47     if(y<=mid)
48         return Query(t<<1,x,y);
49     if(x>mid)
50         return Query(t<<1|1,x,y);
51     else
52         return Query(t<<1,x,mid) + Query(t<<1|1,mid+1,y);
53 }
54 
55 void Add(int t,int x,int y,int k)
56 {
57     if(a[t].x==x && a[t].y==y) //不在推到叶子节点，t下的子孙要增加的值存入a[t].add中
58     {
59         a[t].add += k;
60         a[t].sum += (a[t].y-a[t].x+1)*k;
61         return ;
62     }
63     a[t].sum += (y-x+1)*k;
64     Push_down(t);
65     int mid = (a[t].x+a[t].y)/2;
66     if(y<=mid)
67         Add(t<<1,x,y,k);
68     else if(x>mid)
69         Add(t<<1|1,x,y,k);
70     else
71     {
72         Add(t<<1,x,mid,k);
73         Add(t<<1|1,mid+1,y,k);
74     }
75 }
76 
77 int main()
78 {
79     int n,m;
80     char ch;
81     int x,y,k;
82     scanf("%d %d",&n,&m);
83     Build(1,1,n);
84     while(m--)
85     {
86         getchar();
87         scanf("%c %d %d",&ch,&x,&y);
88         if(ch=='Q')
89             printf("%lld
",Query(1,x,y));
90         else
91         {
92             scanf("%d",&k);
93             Add(1,x,y,k);
94         }
95     }
96     return 0;
97 }