本文主要是介绍NotOnlySuccess大神的飘逸版线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
吐槽：在模板题，我的丑陋的线段树跑了984ms，而大神的只跑了364ms，看来我的代码还是太丑了QAQ
大神的线段树也没什么大优化，就是不知道为什么超级快，或许是我以前看的线段树代码不好吧。。。
我推荐这个线段树的主要原因就是非常好写，空间也是非常小，思路极其清晰。
好了，废话不多说，直接上代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=100001;
ll sum[maxn<<2];
ll add[maxn<<2];
inline void pushup(int rt){sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void build(int l,int r,int rt){if(l==r){scanf("%lld",&sum[rt]);return;}int mid=(l+r)>>1;build(l,mid,rt<<1);build(mid+1,r,rt<<1|1);pushup(rt);
}
inline void pushdown(int rt,int len){if(add[rt]){add[rt<<1]+=add[rt];add[rt<<1|1]+=add[rt];sum[rt<<1]+=add[rt]*(len-(len>>1));sum[rt<<1|1]+=add[rt]*(len>>1);add[rt]=0;}
}
void update(int L,int R,int c,int l,int r,int rt){if(L<=l&&r<=R){add[rt]+=c;sum[rt]+=c*(r-l+1);return;}pushdown(rt,r-l+1);int mid=(l+r)>>1;if(L<=mid)update(L,R,c,l,mid,rt<<1);if(mid+1<=R)update(L,R,c,mid+1,r,rt<<1|1);pushup(rt);
}
ll query(int L,int R,int l,int r,int rt){if(L<=l&&r<=R){return sum[rt];}pushdown(rt,r-l+1);ll ans=0;int mid=(l+r)>>1;if(L<=mid)ans+=query(L,R,l,mid,rt<<1);if(mid+1<=R)ans+=query(L,R,mid+1,r,rt<<1|1);return ans;
}
int main(){int n,m;scanf("%d %d",&n,&m);build(1,n,1);for(int i=1;i<=m;i++){int g;scanf("%d",&g);if(g&1){int l,r;ll c;scanf("%d %d %lld",&l,&r,&c);update(l,r,c,1,n,1);}else{int l,r;scanf("%d %d",&l,&r);printf("%lld\n",query(l,r,1,n,1));}}return 0;
}以上是区间加+区间和
下面是区间加+区间乘+区间和：（这代码好难调啊）
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=100001;
ll p;
ll sum[maxn<<2];
ll add[maxn<<2];
ll mul[maxn<<2];
inline void pushup(int rt){sum[rt]=(sum[rt<<1]+sum[rt<<1|1])%p;
}
inline void mark(int l,int r,int rt,ll a,ll b){sum[rt]=(sum[rt]*a+(r-l+1)*b)%p;mul[rt]=(mul[rt]*a)%p;add[rt]=(add[rt]*a+b)%p;
}
inline void pushdown(int l,int r,int rt){if(mul[rt]!=1||add[rt]!=0){int mid=(l+r)>>1;mark(l,mid,rt<<1,mul[rt],add[rt]);mark(mid+1,r,rt<<1|1,mul[rt],add[rt]);add[rt]=0;mul[rt]=1;}
}
void build(int l,int r,int rt){mul[rt]=1;if(l==r){scanf("%lld",&sum[rt]);return;}int mid=(l+r)>>1;build(l,mid,rt<<1);build(mid+1,r,rt<<1|1);pushup(rt);
}
void update(int L,int R,int l,int r,int rt,ll a,ll b){if(L<=l&&r<=R){mark(l,r,rt,a,b);return;}pushdown(l,r,rt);int mid=(l+r)>>1;if(L<=mid)update(L,R,l,mid,rt<<1,a,b);if(mid+1<=R)update(L,R,mid+1,r,rt<<1|1,a,b);pushup(rt);
}
ll query(int L,int R,int l,int r,int rt){if(L<=l&&r<=R){return sum[rt]%p;}pushdown(l,r,rt);ll ans=0;int mid=(l+r)>>1;if(L<=mid)ans+=query(L,R,l,mid,rt<<1);if(mid+1<=R)ans+=query(L,R,mid+1,r,rt<<1|1);return ans%p;
}
int main(){int n,m;scanf("%d %d %lld",&n,&m,&p);build(1,n,1);for(int i=1;i<=m;i++){int g;scanf("%d",&g);if(g==1){int l,r;ll c;scanf("%d %d %lld",&l,&r,&c);update(l,r,1,n,1,c,0);}else if(g==2){int l,r;ll c;scanf("%d %d %lld",&l,&r,&c);update(l,r,1,n,1,1,c);}else{int l,r;scanf("%d %d",&l,&r);printf("%lld\n",query(l,r,1,n,1));}}return 0;
}end
这篇关于NotOnlySuccess大神的飘逸版线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
