poj 3468 A Simple Problem with Integers (线段树区间更新求和lazy思想)

A Simple Problem with Integers

Time Limit: 5000MS Memory Limit: 131072K

Total Submissions: 75541 Accepted: 23286

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
4
55
9
15
Hint

The sums may exceed the range of 32-bit integers.

Source

POJ Monthly--2007.11.25, Yang Yi

朴素的向下更新会产生很多不必要的操作，所以lazy思想便是，用到再更新，不用就暂存到当前区间。

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <stdlib.h>
  4 #include <math.h>
  5 #include <iostream>
  6 #include <algorithm>
  7 #include <climits>
  8 #include <queue>
  9 #define ll long long
 10 
 11 using namespace std;
 12 
 13 //lazy思想的线段树区间更新，区间查询，感觉不难
 14 
 15 const int MAX = 200005;
 16 ll num[MAX];
 17 
 18 struct nodes
 19 {
 20     int left,right;
 21     ll large,add;
 22 } tree[MAX*5];
 23 
 24 void pushup(int root)//代替递归向上更新
 25 {
 26     tree[root].large = tree[root*2].large + tree[root*2+1].large;
 27 }
 28 void pushdown(int root)//递归向下更新
 29 {
 30     if(tree[root].add)
 31     {
 32         tree[root*2].add += tree[root].add;
 33         tree[root*2+1].add += tree[root].add;
 34         tree[root*2].large += tree[root].add * (tree[root*2].right - tree[root*2].left + 1);
 35         tree[root*2+1].large += tree[root].add * (tree[root*2+1].right - tree[root*2+1].left + 1);
 36         tree[root].add = 0;
 37     }
 38 }
 39 void build(int root,int left,int right)//建树过程，也是初始化更新过程
 40 {
 41     tree[root].left = left;
 42     tree[root].right = right;
 43     tree[root].add = 0;//不能忘记这个值的初始化为0
 44     if(left == right)
 45     {
 46          tree[root].large = num[left];
 47          return;//注意这里的递归结束条件
 48     }
 49 
 50    int mid = (left+right)/2;
 51 
 52     build(2*root,left,mid);
 53     build(2*root+1,mid+1,right);
 54 
 55     pushup(root);//该子区间建立好后，该区间更新
 56 }
 57 
 58 void update(int root,int left,int right,ll val)
 59 {
 60     if(left == tree[root].left && right == tree[root].right) // 刚好进入到所需区间，就可以更新到当前区间直接返回
 61        {
 62            tree[root].add += val; // 用当前节点的add变量记录区间每个元素的累加量
 63            tree[root].large += val * (right - left + 1);//更新当前区间和
 64            return;
 65        }
 66     pushdown(root); //否则向下更新一层，继续找合适区间
 67     int mid = (tree[root].left+tree[root].right)/2;
 68     if(left <= mid && right > mid)
 69     {
 70         update(2*root,left,mid,val);
 71         update(2*root+1,mid+1,right,val);
 72     }
 73     else if(left > mid)
 74     {
 75         update(2*root+1,left,right,val);
 76     }
 77     else
 78     {
 79         update(2*root,left,right,val);
 80     }
 81     pushup(root);
 82 }
 83 
 84 
 85 ll query(int root ,int left,int right)
 86 {
 87     if(left == tree[root].left && right == tree[root].right) //如果是合适区间，直接返回节点值
 88     {
 89         return  tree[root].large;
 90     }
 91     pushdown(root); //否则向下更新一层，继续查找合适区间
 92     int mid = (tree[root].left+tree[root].right)/2;
 93     ll ans = 0;
 94     if(right > mid && left <= mid)
 95     {
 96         ans += query(2*root,left,mid);
 97         ans += query(2*root+1,mid+1,right);
 98     }
 99     else if(left > mid)
100     {
101         ans += query(2*root+1,left,right);
102     }
103     else
104     {
105         ans += query(2*root,left,right);
106     }
107     return ans;
108 }
109 
110 int main(void)
111 {
112     int n,q,i,x,y;
113     ll c;
114     char cmd;
115     scanf("%d %d",&n,&q);
116     for(i = 1; i <= n; i++)
117         scanf("%lld",&num[i]);
118     build(1,1,n);
119     for(i = 0; i < q; i++)
120     {
121         getchar();
122         scanf("%c",&cmd);
123         if(cmd == 'Q')
124         {
125             scanf("%d %d",&x,&y);
126             printf("%lld
",query(1,x,y));
127         }
128         else
129         {
130             scanf("%d %d %lld",&x,&y,&c);
131             update(1,x,y,c);
132         }
133     }
134     return 0;
135 }

Time Limit: 5000MS		Memory Limit: 131072K
Total Submissions: 75541		Accepted: 23286
Case Time Limit: 2000MS