呓语 | 杨英明的个人博客

专注于c++、Python,欢迎交流

By

poj 3468:A Simple Problem with Integers(线段树,区间修改求和

A Simple Problem with Integers
Time Limit: 5000MS   Memory Limit: 131072K
Total Submissions: 58269   Accepted: 17753
Case Time Limit: 2000MS

Description

You have N integers, A1A2, ... , AN. 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 A1A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of AaAa+1, ... , Ab. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of AaAa+1, ... , Ab.

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

 
  线段树,区间修改求和
  题意
  
  思路
  
 
  代码
  1 #include <iostream>
  2 #include <stdio.h>
  3 using namespace std;
  4 
  5 #define MAXN 100010
  6 
  7 struct Node{
  8     long long  L,R;
  9     long long sum;    //当前区间的所有数的和
 10     long long inc;    //累加量
 11 }a[MAXN*3];
 12 
 13 void Build(long long  d,long long  l,long long  r)    //建立线段树
 14 {
 15 
 16     //初始化当前节点的信息
 17     a[d].L = l;
 18     a[d].R = r;
 19     a[d].inc = 0;
 20 
 21     if(l==r){    //找到叶子节点
 22         scanf("%I64d",&a[d].sum);
 23         return ;
 24     }
 25 
 26     //建立线段树
 27     long long  mid = (l+r)>>1;
 28     Build(d<<1,l,mid);
 29     Build(d<<1|1,mid+1,r);
 30 
 31     //更新当前节点的信息
 32     a[d].sum =  a[d<<1].sum + a[d<<1|1].sum;
 33 }
 34 
 35 void Updata(long long  d,long long  l,long long  r,long long  v)    //更新区间[l,r]的累加量为v
 36 {
 37     if(a[d].L==l && a[d].R==r){    //找到终止节点
 38         a[d].inc += v;
 39         return ;
 40     }
 41 
 42     long long  mid = (a[d].L+a[d].R)/2;
 43     a[d].sum += a[d].inc*(a[d].R - a[d].L + 1);
 44 
 45     if(mid>=r){    //左孩子找
 46         Updata(d<<1,l,r,v);
 47     }
 48     else if(mid<l){    //右孩子找
 49         Updata(d<<1|1,l,r,v);
 50     }
 51     else{    //左孩子、右孩子都找
 52         Updata(d<<1,l,mid,v);
 53         Updata(d<<1|1,mid+1,r,v);
 54     }
 55 
 56     a[d].sum = a[d<<1].sum + a[d<<1|1].sum
 57             +  a[d<<1].inc*(a[d<<1].R - a[d<<1].L + 1)
 58             +  a[d<<1|1].inc*(a[d<<1|1].R - a[d<<1|1].L + 1);
 59 }
 60 
 61 long long  Query(long long  d,long long  l,long long  r)    //查询区间[l,r]的所有数的和
 62 {
 63     if(a[d].L==l && a[d].R==r){    //找到终止节点
 64         return  a[d].sum + a[d].inc * (r-l+1);
 65     }
 66 
 67     long long  mid = (a[d].L+a[d].R)/2;
 68     //更新每个节点的sum
 69     a[d].sum += a[d].inc * (a[d].R - a[d].L + 1);
 70     a[d<<1].inc += a[d].inc;
 71     a[d<<1|1].inc += a[d].inc;
 72     a[d].inc = 0;
 73 
 74     //Updata(d<<1,a[d<<1].L,a[d<<1].R,a[d].inc);
 75     //Updata(d<<1|1,a[d<<1|1].L,a[d<<1|1].R,a[d].inc);
 76 
 77     if(mid>=r){    //左孩子找
 78         return Query(d<<1,l,r);
 79     }
 80     else if(mid<l){    //右孩子找
 81         return Query(d<<1|1,l,r);
 82     }
 83     else{    //左孩子、右孩子都找
 84         return Query(d<<1,l,mid) + Query(d<<1|1,mid+1,r);
 85     }
 86     a[d].sum = a[d<<1].sum + a[d<<1|1].sum
 87             +  a[d<<1].inc*(a[d<<1].R - a[d<<1].L + 1)
 88             +  a[d<<1|1].inc*(a[d<<1|1].R - a[d<<1|1].L + 1);
 89 }
 90 
 91 int  main()
 92 {
 93     long long  n,q,A,B;
 94     long long  v;
 95     scanf("%I64d%I64d",&n,&q);
 96     Build(1,1,n);
 97     while(q--){    //q次询问
 98         char c[10];
 99         scanf("%s",&c);
100         switch(c[0]){
101         case 'Q':
102             scanf("%I64d%I64d",&A,&B);
103             printf("%I64d\n",Query(1,A,B));    //输出区间[A,B]所有数的和
104             break;
105         case 'C':
106             scanf("%I64d%I64d%I64d",&A,&B,&v);
107             Updata(1,A,B,v);
108             break;
109         default:break;
110         }
111     }
112     return 0;
113 }

 

Freecode : www.cnblogs.com/yym2013

##原创声明 **转载请注明:[呓语](http://www.yangyingming.com) » [poj 3468:A Simple Problem with Integers(线段树,区间修改求和](http://www.yangyingming.com/article/61)**