终于再过线段树。
参考可禾大神的线段树，然后在down的时候把 add[root*2]+=add[root] 打成了 add[root+2]+=add[root]； 调了一个下午，还被嘲讽。
对于区间修改主要用的是Lazy Tag，把增量延迟下方。
可以达到O（nlogn）。
这次代码里有注释。
#include<cstdio> using namespace std; typedef long long LL; const int N=100005; LL seg[N*4+10],add[N*4+10],a[N],n,q,x,y,z,c,i; inline void read(LL &x) { x=0; char ch=getchar(); int flag=1; while (ch<'0'||ch>'9') { if (ch=='0') flag=-1; ch=getchar(); } while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); x*=flag; } inline void write(LL x) { if (x/10) write(x/10); putchar(x%10+'0'); } inline void up(LL root) { seg[root]=seg[root*2]+seg[root*2+1]; } //向上传递信息 inline void down(LL root,LL l,LL r) //延迟标记下传 { if (add[root]) { add[root*2]+=add[root]; add[root*2+1]+=add[root]; seg[root*2]+=add[root]*l; seg[root*2+1]+=add[root]*r; add[root]=0; } } inline void build(LL root,LL l,LL r) //递归建边，注意要向上传递 { if (l==r) seg[root]=a[l]; else { LL mid=l+r>>1; build(root*2,l,mid); build(root*2+1,mid+1,r); up(root); } } inline LL query(LL root,LL l,LL r,LL ql,LL qr) //区间求和，标记下传！！！ { if (l>=ql&&r<=qr) return seg[root]; else { LL mid=l+r>>1; down(root,mid-l+1,r-mid); LL res=0; if (ql<=mid) res+=query(root*2,l,mid,ql,qr); if (mid<qr) res+=query(root*2+1,mid+1,r,ql,qr); return res; } } inline void change(LL root,LL l,LL r,LL ql,LL qr,LL v) //区间修改，线段树的核心，注意修改之后既会影响到它的父节点，也影响到它的儿子 { if (l>=ql&&r<=qr) { seg[root]+=(r-l+1)*v; add[root]+=v; } else { LL mid=l+r>>1; down(root,mid-l+1,r-mid); if (ql<=mid) change(root*2,l,mid,ql,qr,v); if (mid<qr) change(root*2+1,mid+1,r,ql,qr,v); up(root); } } int main() { read(n); read(q); for (i=1;i<=n;++i) read(a[i]); build(1,1,n); while (q--) { read(c); if (c==1) { read(x); read(y); read(z); change(1,1,n,x,y,z); } else { read(x); read(y); write(query(1,1,n,x,y)); putchar(' '); } } return 0; }