原题
//codevs1082 线段树练习3 #include<iostream> #include<cstdio> #include<cstring> #define lson l,m,pos<<1 #define rson m+1,r,pos<<1|1 #define ll long long using namespace std; int n,m; ll sum[8010000],col[8010000]; void pushup(int pos){sum[pos]=sum[pos<<1]+sum[pos<<1|1];} void pushdown(int pos,int len) { if (col[pos]) { col[pos<<1]+=col[pos];col[pos<<1|1]+=col[pos]; sum[pos<<1]+=col[pos]*(len-(len>>1)); sum[pos<<1|1]+=col[pos]*(len>>1); col[pos]=0; } } void build(int l,int r,int pos) { col[pos]=0; if (l==r) {scanf("%lld",&sum[pos]); return;} int m=(l+r)>>1; build(lson);build(rson); pushup(pos); } void update(int L,int R,ll add,int l,int r,int pos) { if (L<=l&&r<=R) { col[pos]+=add; sum[pos]+=add*(r-l+1); return; } int m=(l+r)>>1; pushdown(pos,r-l+1); if (L<=m) update(L,R,add,lson); if (R>m) update(L,R,add,rson); pushup(pos); } ll query(int L,int R,int l,int r,int pos) { if (L<=l&&r<=R) return sum[pos]; pushdown(pos,r-l+1);//询问的时候下放标记 int m=(l+r)>>1;ll ret=0; if (L<=m) ret+=query(L,R,lson); if (R>m) ret+=query(L,R,rson);//再写错我就剁烂自己的手 return ret; } int main() { scanf("%d",&n); build(1,n,1); scanf("%d",&m); while(m--) { int order,a,b;ll c; scanf("%d",&order); if (order==1) { scanf("%d%d%lld",&a,&b,&c); update(a,b,c,1,n,1); } else scanf("%d%d",&a,&b),printf("%lld\n",query(a,b,1,n,1)); } return 0; }
