TLE就是因为没有标记持久化啊，如果没有标记的话那么每一次修改都要访问到最底层……
建议还是去学一下。其实标记持久化的意思是，如果我当前没有访问子节点的必要，我就可以将两个子节点需要修改的数据保留在父亲处，等到有需要的时候一起修改
by Small_Tang @ 2021-09-11 14:31:09
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define il inline
const LL MAXN=111111;
struct node
{
LL l,r,v,add,mid,lazy;//v是初值，add是加的数值,lazy是持久化标记
};
LL input[MAXN];
struct segmentTree
{
node T[MAXN*4];
il void init(LL s,LL t,LL o)
{
T[o].l=s,T[o].r=t,T[o].mid=T[o].l+((T[o].r-T[o].l)>>1);
T[o].lazy=0;
if(T[o].l==T[o].r) {T[o].v=input[T[o].l];return;}
init(s,T[o].mid,o<<1);init(T[o].mid+1,t,o<<1|1);
T[o].v=T[o<<1].v+T[o<<1|1].v;
}
il void down(LL o)
{
T[o<<1].add+=(T[o<<1].r-T[o<<1].l+1)*T[o].lazy;
T[o<<1].lazy+=T[o].lazy;
T[o<<1|1].add+=(T[o<<1|1].r-T[o<<1|1].l+1)*T[o].lazy;
T[o<<1|1].lazy+=T[o].lazy;
T[o].lazy=0;
}
il void update_P(LL s,LL t,LL o,LL k)
{
LL l=T[o].l,r=T[o].r;
if(s<=T[o].l && T[o].r<=t){T[o].add+=(r-l+1)*k;T[o].lazy+=k;return;}
if(T[o].lazy)down(o);
if(s<=T[o].mid) update_P(s,t,o<<1,k);if(t>T[o].mid) update_P(s,t,o<<1|1,k);
T[o].add=T[o<<1].add+T[o<<1|1].add;
}
il LL query(LL s,LL t,LL o)
{
LL ans=0;
if(s<=T[o].l && T[o].r<=t) return T[o].v+T[o].add;
if(T[o].lazy)down(o);
if(s<=T[o].mid) ans+=query(s,t,o<<1);if(T[o].mid<t) ans+=query(s,t,o<<1|1);
return ans;
}
}ST;
LL n,m,op,x,y,k;
int main()
{
// freopen("P3372_8.in","r",stdin);
// freopen("P3372_8.out","w",stdout);
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(LL i=1;i<=n;i++) cin>>input[i];
ST.init(1,n,1);
while(m--)
{
cin>>op;
if(op==1)
{
cin>>x>>y>>k;ST.update_P(x,y,1,k);
}
else if(op==2)
{
cin>>x>>y;cout<<ST.query(x,y,1)<<endl;
}
}
return 0;
}
```
加了懒标记，AC了
加油
~~(日行一善，RP++)~~
by 陈总 @ 2021-09-11 14:55:56
@[陈总](/user/92554) %%%
by Small_Tang @ 2021-09-11 14:57:00
@[陈总](/user/92554) 多谢神犇
by 2020kanade @ 2021-09-12 13:21:04
@[Summery](/user/362243) 确实
昨天看了一晚上题解总算懂了
by 2020kanade @ 2021-09-12 13:22:05
结贴
昨天寝室里学习了半晚上总算懂了，我原来写的怕是个四不像
（其实add是标记，但是没想到搞下传......）
by 2020kanade @ 2021-09-12 14:00:33