You have N integers, A1, A2, ... , 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 A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of Aa, Aa+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
1 #include <iostream> 2 //#include<bits/stdc++.h> 3 #include <stack> 4 #include <queue> 5 #include <cstdio> 6 #include <cstring> 7 #include <algorithm> 8 using namespace std; 9 typedef long long ll; 10 typedef unsigned long long ull; 11 const int MAX=1e5+5; 12 struct node 13 { 14 int left,right,mid; 15 ll sum; 16 ll lazy; 17 }st[10*MAX]; 18 void pushup(int k)//向上刷新 19 { 20 st[k].sum=st[2*k].sum+st[2*k+1].sum; 21 } 22 void init(int l,int r,int k)//比较好的初始数据方式 23 { 24 st[k].left=l; 25 st[k].right=r; 26 st[k].mid=(l+r)/2; 27 st[k].sum=st[k].lazy=0; 28 if(l+1==r) 29 { 30 scanf("%I64d",&st[k].sum); 31 return; 32 } 33 init(l,(l+r)/2,2*k); 34 init((l+r)/2,r,2*k+1); 35 pushup(k); 36 } 37 void pushdown(int k)//向下刷新 38 { 39 if(st[k].lazy!=0) 40 { 41 st[2*k].lazy+=st[k].lazy; 42 st[2*k+1].lazy+=st[k].lazy; 43 st[2*k].sum+=(st[2*k].right-st[2*k].left)*st[k].lazy; 44 st[2*k+1].sum+=(st[2*k+1].right-st[2*k+1].left)*st[k].lazy; 45 st[k].lazy=0; 46 } 47 } 48 void update(int l,int r,int c,int k)//[l,r]区间加c 49 { 50 if(st[k].left>=r||st[k].right<=l) 51 return; 52 if(st[k].left>=l&&st[k].right<=r) 53 { 54 st[k].sum+=(st[k].right-st[k].left)*c; 55 st[k].lazy+=c; 56 return; 57 } 58 pushdown(k); 59 update(l,r,c,2*k); 60 update(l,r,c,2*k+1); 61 st[k].sum=st[2*k].sum+st[2*k+1].sum; 62 return; 63 } 64 ll query(int trl,int trr,int ptl,int ptr,int k)//询问[trl,trr]区间和的函数 65 { 66 if(ptr<=trl||ptl>=trr) 67 return 0; 68 if(ptl+1==ptr||(ptl>=trl&&ptr<=trr)) 69 return st[k].sum; 70 71 pushdown(k); 72 if(ptl>=trl&&ptr<=trr) 73 return st[k].sum; 74 return query(trl,trr,ptl,(ptl+ptr)/2,2*k)+query(trl,trr,(ptl+ptr)/2,ptr,2*k+1); 75 } 76 char tem[10]; 77 int main() 78 { 79 int n,q; 80 scanf("%d %d",&n,&q); 81 init(1,n+1,1); 82 int i,j,z; 83 while(q--) 84 { 85 scanf("%s %d %d",tem,&i,&j); 86 if(tem[0]==‘Q‘) 87 printf("%I64d\n",query(i,j+1,1,n+1,1)); 88 else 89 { 90 scanf("%d",&z); 91 update(i,j+1,z,1); 92 } 93 } 94 }
（线段树）poj3468-A Simple Problem with Integers
原文：http://www.cnblogs.com/quintessence/p/6411341.html