hdu1698（区间修改） 传送门
#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,c,sum[400005],lazy[400005];
void build(int l,int r,int pos)//建树
{if(l==r){sum[pos]=1;return;}int mid=(r+l)/2;build(l,mid,pos*2);build(mid+1,r,pos*2+1);sum[pos]=sum[pos*2]+sum[pos*2+1];
}
void pushdown(int l,int r,int pos)//标记 下传
{if(lazy[pos]!=0)//如果这个点可以被更改 {int mid=(l+r)/2;lazy[pos*2]=lazy[pos*2+1]=lazy[pos];//那么他的俩个儿子也应该被更改，更改的数也就是lazy sum[pos*2]=(mid-l+1)*lazy[pos];//俩个儿子的区间的数不也就是俩个区间乘以lazy sum[pos*2+1]=(r-mid)*lazy[pos];lazy[pos]=0;//这个数改过了 }
}
void update(int l,int r,int L,int R,int v,int pos)
{if(L>=l&&R<=r)//如果这个区间属于要更改的区间 {lazy[pos]=v;//要更改的数赋给lazy sum[pos]=(R-L+1)*v;//这个区间的数的和不就是长度乘以v return;//表示这个区间被标记完了 可以去上一层了 }pushdown(L,R,pos);//下传 int mid=(R+L)/2;if(l<=mid)//如果区间有部分在左区间 update(l,r,L,mid,v,pos*2);if(r>mid)//如果区间有部分在右区间 update(l,r,mid+1,R,v,pos*2+1);sum[pos]=sum[pos*2]+sum[pos*2+1];
}
int main()
{int t;scanf("%d",&t);int k=0;while(t--){memset(sum,0,sizeof(sum));memset(lazy,0,sizeof(lazy));scanf("%d%d",&n,&m);build(1,n,1);while(m--){scanf("%d%d%d",&a,&b,&c);update(a,b,1,n,c,1); }printf("Case %d: The total value of the hook is %d.\n",++k,sum[1]);}return 0;
}洛谷 线段树模板1 传送门
#include<bits/stdc++.h>
using namespace std;
long long int sum[100000*4], lazy[100000*4],n,m,x,y,z,a[100005],p;
void build(long long int l,long long int r,long long int pos)//建树
{if(r==l){sum[pos]=a[l];return;}long long int mid=(r+l)/2;build(l,mid,pos*2);build(mid+1,r,pos*2+1);sum[pos]=sum[pos*2]+sum[pos*2+1];
}
void pushdown(long long int l,long long int r,long long int pos)//下传
{if(lazy[pos]!=0){long long int mid=(r+l)/2;lazy[pos*2]+=lazy[pos];lazy[pos*2+1]+=lazy[pos];sum[pos*2]+=(mid-l+1)*lazy[pos];sum[pos*2+1]+=(r-mid)*lazy[pos];lazy[pos]=0;}
}
void update(long long int l,long long int r,long long int L,long long int R,long long int v,long long int pos)//更新 加v
{if(l<=L&&r>=R){lazy[pos]+=v;sum[pos]+=(R-L+1)*v;return;}long long int mid=(R+L)/2;pushdown(L,R,pos);if(l<=mid)update(l,r,L,mid,v,pos*2);if(r>mid)update(l,r,mid+1,R,v,pos*2+1);sum[pos]=sum[pos*2]+sum[pos*2+1];
}
long long query(long long int l,long long int r,long long int L,long long int R,long long int pos)//查找
{long long res=0;if(l<=L&&r>=R)return sum[pos];long long mid=(L+R)/2;pushdown(L,R,pos);if(l<=mid)//如果有数在左边的话 左边部分查找 res+=query(l,r,L,mid,pos*2);if(r>mid)//如果有数在右边 右边部分查找 res+=query(l,r,mid+1,R,pos*2+1);return res;
}
int main()
{scanf("%lld %lld",&n,&m);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);build(1,n,1);while(m--){scanf("%lld",&p);if(p==1){scanf("%lld%lld%lld",&x,&y,&z);update(x,y,1,n,z,1);}else{scanf("%lld %lld",&x,&y);printf("%lld\n",query(x,y,1,n,1));}}
} 洛谷 线段树模板二 区间更改的乘法修改和加法修改同时存在 以乘法的优先级更高来处理
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
long long n,m,mod,x,y,z,op,sum[maxn*4],mul[maxn*4],add[maxn*4],a[maxn];
void build(long long l,long long r,long long res)
{mul[res]=1;add[res]=0;if(l==r){sum[res]=a[l];return;}long long mid=(l+r)/2;build(l,mid,res*2);build(mid+1,r,res*2+1);sum[res]=sum[res*2]+sum[res*2+1];sum[res]%=mod;
}
void pushdown(long long l,long long r,long long res)
{long long mid=(l+r)/2;sum[res*2]=(sum[res*2]*mul[res]+add[res]*(mid-l+1))%mod;sum[res*2+1]=(sum[res*2+1]*mul[res]+add[res]*(r-mid))%mod;mul[res*2]=(mul[res*2]*mul[res])%mod;mul[res*2+1]=(mul[res*2+1]*mul[res])%mod;add[res*2]=(add[res*2]*mul[res]+add[res])%mod;add[res*2+1]=(add[res*2+1]*mul[res]+add[res])%mod;mul[res]=1;add[res]=0;
}
void update1(long long l,long long r,long long res,long long L,long long R,long long k)
{if(L<=l&&R>=r){sum[res]=(sum[res]*k)%mod;mul[res]=(mul[res]*k)%mod;add[res]=(add[res]*k)%mod;return;}pushdown(l,r,res);long long mid=(l+r)/2;if(L<=mid) update1(l,mid,res*2,L,R,k);if(R>mid) update1(mid+1,r,res*2+1,L,R,k);sum[res]=(sum[res*2]+sum[res*2+1])%mod;
}
void update2(long long l,long long r,long long res,long long L,long long R,long long k)
{if(L<=l&&R>=r){sum[res]=(sum[res]+k*(r-l+1))%mod;add[res]=(add[res]+k)%mod;return;}pushdown(l,r,res);long long mid=(l+r)/2;if(L<=mid) update2(l,mid,res*2,L,R,k);if(R>mid) update2(mid+1,r,res*2+1,L,R,k);sum[res]=(sum[res*2]+sum[res*2+1])%mod;
}
long long query(long long l,long long r,long long res,long long L,long long R)
{if(L<=l&&R>=r){return sum[res];}pushdown(l,r,res);long long mid=(l+r)/2,ans=0;if(L<=mid) ans=(ans+query(l,mid,res*2,L,R))%mod;if(R>mid) ans=(ans+query(mid+1,r,res*2+1,L,R))%mod;return ans%mod;
}
int main()
{scanf("%lld%lld",&n,&mod);for(long long i=1; i<=n; i++)scanf("%lld",&a[i]);build(1,n,1);scanf("%lld",&m);while(m--){scanf("%lld",&op);if(op==1){scanf("%lld%lld%lld",&x,&y,&z);update1(1,n,1,x,y,z);}else if(op==2){scanf("%lld%lld%lld",&x,&y,&z);update2(1,n,1,x,y,z);}else{scanf("%lld%lld",&x,&y);long long q=query(1,n,1,x,y);printf("%lld\n",q);}}
}