Description
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
The sums may exceed the range of 32-bit integers.Source
POJ Monthly--2007.11.25, Yang Yi
題意：
給出n個數和m個操作，C操作是對[l,r]區間同時加上一個數val，Q操作是查詢[l,r]區間的和。
思路：
線段樹區間更新，需要用到lazy標記，每次更新不用更新到葉子節點，而是更新到一個完整的區間，用一個add[]數組記錄這個區間需加上的數，就不用繼續往下更新了。增加了pushdown和pushup操作，pushdown的作用是將標記下移，這個區間改動了的話，它下面的孩子都會改動，pushup操作是根據孩子重新求該節點的值。（因為每次都pushdown了，所以該節點沒有標記了，所以pushup很簡單）
ps：not only success的風格，只用數組就行了。
每次pushdown的時候最好將孩子的值也更新，不更新可能存在一定的問題。
其實如果對於這種相互之間不用因為順序而影響的更新操作，可以不用pushdown的，query的時候將值依次傳下去即可，但是寫法稍稍麻煩一些，大白上就是這樣寫的，需要注意一些細節問題，個人還是喜歡pushdown的寫法。
代碼：
#include#include #include #include #define maxn 100005 #define lson (rt<<1) #define rson (rt<<1|1) #define INF 0x3f3f3f3f typedef long long ll; using namespace std; int n,m; int a[maxn],add[maxn<<2],sum[maxn<<2]; char s[10]; void pushup(int rt) { sum[rt]=sum[lson]+sum[rson]; } void pushdown(int le,int ri,int rt) { if(add[rt]) { add[lson]+=add[rt]; sum[lson]+=add[rt]*((ri-le+2)>>1); add[rson]+=add[rt]; sum[rson]+=add[rt]*((ri-le+1)/2); add[rt]=0; } } void update(int le,int ri,int rt,int u,int v,int val) { if(le==u&&ri==v) { add[rt]+=val; sum[rt]+=val*(ri-le+1); return ; } int mid=(le+ri)>>1; pushdown(le,ri,rt); if(v<=mid) { update(le,mid,lson,u,v,val); } else if(u>=mid+1) { update(mid+1,ri,rson,u,v,val); } else { update(le,mid,lson,u,mid,val); update(mid+1,ri,rson,mid+1,v,val); } pushup(rt); } int query(int le,int ri,int rt,int u,int v) { if(le==u&&ri==v) { return sum[rt]; } int res=0,mid=(le+ri)>>1; pushdown(le,ri,rt); if(v<=mid) { res=query(le,mid,lson,u,v); } else if(u>=mid+1) { res=query(mid+1,ri,rson,u,v); } else { res+=query(le,mid,lson,u,mid); res+=query(mid+1,ri,rson,mid+1,v); } return res; } int main() { while(~scanf("%d%d",&n,&m)) { memset(sum,0,sizeof(sum)); memset(add,0,sizeof(add)); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); update(1,n,1,i,i,a[i]); } while(m--) { scanf("%s",s); int u,v,val; if(s[0]=='C') { scanf("%d%d%d",&u,&v,&val); update(1,n,1,u,v,val); } else { scanf("%d%d",&u,&v); int ans=query(1,n,1,u,v); printf("%d\n",ans); } } } return 0; } /* 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 */
