题目连接：http://poj.org/problem?id=3468
成断增加，注意的是求和可能超过32位，用__int64存储，成断更新的时候注意color为+-，而不是替换，有可能出现儿子的值还存在没有向下更新。。
#include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #define MAXN 100010 __int64 color[MAXN<<2]; __int64 tree[MAXN<<2]; int n,num; void build_tree(int l,int r,int id); void push_up_tree(int id); __int64 query_tree(int left,int right,int l,int r,int id); void update_tree(int left,int right,int l,int r,int id,__int64 value); void push_down(int l,int r,int id); int main() { int i,left,right; __int64 value; char str[10]; while(scanf("%d%d",&n,&num)==2) { build_tree(1,n,1); //printf("%I64d\n",tree[4]); for(i=1;i<=num;i++) { scanf("%s",str); if(str[0]=='Q') { scanf("%d%d",&left,&right); // printf("%s %d %d\n",str,left,right); printf("%I64d\n",query_tree(left,right,1,n,1)); } if(str[0]=='C') { scanf("%d%d%I64d",&left,&right,&value); update_tree(left,right,1,n,1,value); } } } } void build_tree(int l,int r,int id) { color[id]=0; if(l==r) { scanf("%I64d",&tree[id]); return ; } int mid=l+r>>1; build_tree(l,mid,id<<1); build_tree(mid+1,r,id<<1|1); push_up_tree(id); } void push_up_tree(int id) { tree[id]=tree[id<<1]+tree[id<<1|1]; } __int64 query_tree(int left,int right,int l,int r,int id) { if(left<=l&&right>=r) return tree[id]; push_down(l,r,id); int mid=l+r>>1;__int64 ret0=0; if(left<=mid) ret0+=query_tree(left,right,l,mid,id<<1); if(right>mid) ret0+=query_tree(left,right,mid+1,r,id<<1|1); return ret0; } void push_down(int l,int r,int id) { if(color[id]) { int mid=l+r>>1; color[id<<1]+=color[id]; color[id<<1|1]+=color[id]; tree[id<<1]+=(mid-l+1)*color[id]; tree[id<<1|1]+=(r-mid)*color[id]; color[id]=0; } } void update_tree(int left,int right,int l,int r,int id, __int64 value) { if(left<=l&&right>=r) { color[id]+=value; tree[id]+=(r-l+1)*value; return ; } push_down(l,r,id); int mid=l+r>>1; if(left<=mid) { update_tree(left,right,l,mid,id<<1,value); } if(right>mid) update_tree(left,right,mid+1,r,id<<1|1,value); push_up_tree(id); }