题目链接：
http://poj.org/problem?id=3468
题意：
对于一个区间的数有两种操作：
C a b c 在区间[a,b]内的数全部加上c
Q a b 查询区间[a,b]之间的数的和
解：
嗯，没什么好说的，就直接线段树就行了，需要注意的就是懒惰标记的理解和应用了。
关于懒惰标记的理解推荐这篇博客：http://blog.csdn.net/sdjzping/article/details/19542103
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> using namespace std; const int maxn=1e5+50; typedef long long ll; ll a[maxn];int n; struct Tree{ int node,l,r; ll v,laz; }seg[ maxn << 2 ]; void pushup(int node){ seg[node].v=seg[node<<1].v+seg[node<<1|1].v; } void pushdown(int node,int b){ if(seg[node].laz) { seg[node<<1].laz+=seg[node].laz; seg[node<<1|1].laz+=seg[node].laz; seg[node<<1].v+=(ll)(b-(b/2))*seg[node].laz; seg[node<<1|1].v+=(ll)(b/2)*seg[node].laz; seg[node].laz=0; } } void build(int l,int r,int node){ seg[node].l=l;seg[node].r=r;seg[node].laz=0; if(l==r){ seg[node].v=a[l]; return ; } int mid=(l+r)/2; build(l,mid,node<<1); build(mid+1,r,node<<1|1); pushup(node); } void update(int l,int r,int node,int k){ if(l<=seg[node].l&&seg[node].r<=r) { seg[node].v+=(seg[node].r-seg[node].l+1)*k; seg[node].laz+=k; return ; } pushdown(node,seg[node].r-seg[node].l+1); int mid=(seg[node].l+seg[node].r)/2; if(mid>=l) update(l,r,node<<1,k); if(r>mid) update(l,r,node<<1|1,k); pushup(node); } ll query(int l,int r,int node){ if(l<=seg[node].l&&seg[node].r<=r) { //cout<<"Node:"<<node<<" L:"<<seg[node].l<<" R:"<<seg[node].r<<endl; return seg[node].v; } pushdown(node,seg[node].r-seg[node].l+1); int mid=(seg[node].l+seg[node].r)/2; ll xa=0,xb=0; if(mid>=l) xa=query(l,r,node<<1); if(r>mid) xb=query(l,r,node<<1|1); pushup(node); //cout<<"Node:"<<node<<" Xa:"<<xa<<" Xb:"<<xb<<endl; return xa+xb; } void show(int node){ cout<<"Node:"<<node<<endl; cout<<"L:"<<seg[node].l<<" R:"<<seg[node].r<<endl; cout<<"Value:"<<seg[node].v<<endl; cout<<endl; if(seg[node].l==seg[node].r)return ; show(node<<1); show(node<<1|1); } int main() { int n,q; while(~scanf("%d%d",&n,&q)) { for(int i=1;i<=n;i++) scanf("%I64d",&a[i]); build(1,n,1); while(q--){ char op[2]; int c1,c2; scanf("%s",op); if(op[0]=='C') { int c3; scanf("%d%d%d",&c1,&c2,&c3); update(c1,c2,1,c3); //show(1); } else { scanf("%d%d",&c1,&c2); ll ans=query(c1,c2,1); printf("%I64d\n",ans); } } } return 0; }
