给你N个数，有两种操作：
1：给区间[a,b]的所有数增加X
2：询问区间[a,b]的数的和。
第一行一个正整数n，接下来n行n个整数，
再接下来一个正整数Q，每行表示操作的个数，
如果第一个数是1，后接3个正整数，
表示在区间[a,b]内每个数增加X,如果是2，
表示操作2询问区间[a,b]的和是多少。
对于每个询问输出一行一个答案
3
1
2
3
2
1 2 3 2
2 2 3
9
数据范围
1<=n<=200000
1<=q<=200000
#include<iostream> #include<cstdio> using namespace std; const int maxn=2000000; int tot=0; long long a[3000000]; struct treetype { int Left,Right; //区间[Left,Right) int lptr,rptr; //左右孩子指针 long long sum; //区间和 long long bj; //标记 }t[4*maxn]; void buildtree(int ll,int rr) //建树 { int cur=++tot; t[cur].Left=ll; t[cur].Right=rr; if(ll!=rr-1) { t[cur].lptr=tot+1; buildtree(ll,(ll+rr)/2); t[cur].rptr=tot+1; buildtree((ll+rr)/2,rr); t[cur].sum=t[t[cur].lptr].sum+t[t[cur].rptr].sum; }else t[cur].sum=a[ll]; } void update(int k) //延迟信息下传 { t[t[k].lptr].sum+=t[k].bj*(t[t[k].lptr].Right-t[t[k].lptr].Left); t[t[k].rptr].sum+=t[k].bj*(t[t[k].rptr].Right-t[t[k].rptr].Left); t[t[k].lptr].bj+=t[k].bj; /* */ t[t[k].rptr].bj+=t[k].bj; /* 标记分解 */ t[k].bj=0; /* */ } void change(int k,int ll,int rr,long long delta) //修改区间[ll,rr)元素的值 { if (ll<=t[k].Left&&rr>=t[k].Right) //修改的区间已经覆盖了当前结点 { t[k].sum+=delta*(t[k].Right-t[k].Left); t[k].bj+=delta; //累计修改 } else { if(t[k].bj) update(k); //传递修改 if (ll<(t[k].Left+t[k].Right)/2) change(t[k].lptr,ll,rr,delta); if (rr>(t[k].Left+t[k].Right)/2) change(t[k].rptr,ll,rr,delta); t[k].sum=t[t[k].lptr].sum+t[t[k].rptr].sum; } } long long query(int k,int ll,int rr) //查询[ll,rr)区间和 { if (ll<=t[k].Left&&rr>=t[k].Right) return t[k].sum; if (t[k].bj) update(k); //传递修改 long long ans=0; if (ll<(t[k].Left+t[k].Right)/2) ans+=query(t[k].lptr,ll,rr); if (rr>(t[k].Left+t[k].Right)/2) ans+=query(t[k].rptr,ll,rr); return ans; } int main() { int n; scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%lld",&a[i]); buildtree(1,n+1); scanf("%d",&n); int at,x,y; long long p; for (int i=1;i<=n;i++) { scanf("%d",&at); if (at==1){ scanf("%d%d%lld",&x,&y,&p); change(1,x,y+1,p); } if (at==2){ scanf("%d%lld",&x,&p); printf("%lld\n",query(1,x,p+1)); } } return 0; }
原文：http://www.cnblogs.com/liumengyue/p/5106370.html