果然还是递归线段树好理解啊，写了个模板题，用了黄学长的模板。codevs的线段树练习3.
代码：
#include"iostream" #include"cstdio" using namespace std; struct node{ int s,t,sum,lab; }tr[800001]; int n,q; int a[200001]; int read() { char c=getchar(); int a=0; while (c<'0'||c>'9') c=getchar(); while (c>='0'&&c<='9') { a=a*10+c-'0'; c=getchar(); } return a; } void build(int k,int x,int y) { tr[k].s=x;tr[k].t=y; if (x==y) { tr[k].sum=a[x]; return; } int mid=(x+y)>>1; build(k<<1,x,mid); build(k<<1|1,mid+1,y); tr[k].sum=tr[k<<1].sum+tr[k<<1|1].sum; } void pushdown(int k) { int x=tr[k].t-tr[k].s+1; tr[k<<1].lab+=tr[k].lab; tr[k<<1|1].lab+=tr[k].lab; tr[k<<1].sum+=(x-(x>>1))*tr[k].lab; tr[k<<1|1].sum+=(x>>1)*tr[k].lab; tr[k].lab=0; } void change(int now,int x,int y,int k) { int l=tr[now].s,r=tr[now].t; if (x==l && y==r) { tr[now].lab+=k; tr[now].sum+=(y-x+1)*k; return; } if (tr[now].lab) pushdown(now); int mid=(l+r)>>1; if (x>mid) change(now<<1|1,x,y,k); else if (y<=mid) change(now<<1,x,y,k); else { change(now<<1,x,mid,k); change(now<<1|1,mid+1,y,k); } tr[now].sum=tr[now<<1].sum+tr[now<<1|1].sum; return; } long long ask(int now,int x,int y) { int l=tr[now].s,r=tr[now].t; if (x==l && y==r) return tr[now].sum; if (tr[now].lab) pushdown(now); int mid=(l+r)>>1; if (x>mid) return ask(now<<1|1,x,y); else if (y<=mid) return ask(now<<1,x,y); else return (ask(now<<1,x,mid)+ask(now<<1|1,mid+1,y)); } int main() { n=read(); for (int i=1; i<=n; i++) a[i]=read(); build(1,1,n); q=read(); for (int i=1; i<=q; i++) { int now=read(); if (now==1) { int x=read(),y=read(),k=read(); change(1,x,y,k); } else if (now==2) { int x=read(),y=read(); printf("%lld ",ask(1,x,y)); } } return 0; }