简单实用的数据结构——线段树（模板）
一.基本操作，查询区间最大最小值（传送门）
#include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<algorithm> #include<stack> #include<queue> #include<iostream> #include<deque> #include<vector> #include<map> #include<set> using namespace std; #define maxn 2000000 int n,q; int a[maxn]; int sum_max[maxn<<2]; int sum_min[maxn<<2]; inline int lck(int o,int p) { return o>p?o:p; } inline int syf(int o,int p) { return o<p?o:p; } inline int read() { char kr=0; char ls; for(;ls>'9'||ls<'0';kr=ls,ls=getchar()); int xs=0; for(;ls>='0'&&ls<='9';ls=getchar()) { xs=xs*10+ls-48; } if(kr=='-') xs=0-xs; return xs; } inline int build_summax(int k,int l,int r) { if(l==r) return sum_max[k]=a[l]; int mid=l+r>>1; if(l<=mid) build_summax(k<<1,l,mid); if(mid<r) build_summax(k<<1|1,mid+1,r); sum_max[k]=lck(sum_max[k<<1],sum_max[k<<1|1]); } inline int build_summin(int k,int l,int r) { if(l==r) return sum_min[k]=a[l]; int mid=l+r>>1; if(l<=mid) build_summin(k<<1,l,mid); if(mid<r) build_summin(k<<1|1,mid+1,r); sum_min[k]=syf(sum_min[k<<1],sum_min[k<<1|1]); } inline int query_max(int k,int l,int r,int x,int y) { int INF=-99999999; if(l>y||r<x) return -99999999; if(l>=x&&r<=y) return sum_max[k]; int mid=l+r>>1; int INF1,INF2; if(l<=mid) INF1=query_max(k<<1,l,mid,x,y); if(mid<r) INF2=query_max(k<<1|1,mid+1,r,x,y); return INF=lck(INF,lck(INF1,INF2)); } inline int query_min(int k,int l,int r,int x,int y) { int INF=99999999; if(l>y||r<x) return 99999999; if(l>=x&&r<=y) return sum_min[k]; int mid=l+r>>1; int INF1,INF2; if(l<=mid) INF1=query_min(k<<1,l,mid,x,y); if(mid<r) INF2=query_min(k<<1|1,mid+1,r,x,y); return INF=syf(INF,syf(INF1,INF2)); } int main() { memset(sum_max,-99999999,sizeof(sum_max)); memset(sum_min,99999999,sizeof(sum_min)); n=read();q=read(); for(int i=1;i<=n;i++) { a[i]=read(); } build_summax(1,1,n); build_summin(1,1,n); int x,y; for(int i=1;i<=q;i++) { x=read();y=read(); int maxx=query_max(1,1,n,x,y); int minn=query_min(1,1,n,x,y); printf("%d ",maxx-minn); } return 0; }
二.线段树区间加法，区间求和（传送门）
#include<iostream> #include<cstdio> #include<algorithm> #include<set> #include<cstring> #include<string> #include<deque> #include<map> #include<cmath> #include<stack> #include<vector> #include<queue> #include<cstdlib> using namespace std; #define lck_max(a,b) ((a)>(b)?(a):(b)) #define lck_min(a,b) ((a)<(b)?(a):(b)) typedef long long LL; const int maxn=1e5+7; LL n,m,flag,a[maxn],sum[maxn<<2],add[maxn<<2]; inline LL read() { LL kr=1,xs=0; char ls; ls=getchar(); while(!isdigit(ls)) { if(!(ls^45)) kr=-1; ls=getchar(); } while(isdigit(ls)) { xs=(xs<<1)+(xs<<3)+(ls^48); ls=getchar(); } return xs*kr; } void out(LL xs) { if(xs<0) putchar('-'),xs=-xs; if(xs>9) out(xs/10); putchar(xs%10+'0'); } void build_sum(LL k,LL l,LL r) { if(l==r) {sum[k]=a[l];return ;} LL mid=l+r>>1; if(l<=mid) build_sum(k<<1,l,mid); if(mid<r) build_sum(k<<1|1,mid+1,r); sum[k]=sum[k<<1]+sum[k<<1|1]; } inline void add_sum(LL k,LL l,LL r,LL v) { add[k]+=v; sum[k]+=(r-l+1)*v; return ; } inline void push_down(LL k,LL l,LL r,LL mid) { if(!add[k]) return ; add_sum(k<<1,l,mid,add[k]); add_sum(k<<1|1,mid+1,r,add[k]); add[k]=0; } void change(LL k,LL l,LL r,LL x,LL y,LL v) { if(l>=x&&r<=y) return add_sum(k,l,r,v); LL mid=l+r>>1; push_down(k,l,r,mid); if(x<=mid) change(k<<1,l,mid,x,y,v); if(mid<y) change(k<<1|1,mid+1,r,x,y,v); sum[k]=sum[k<<1]+sum[k<<1|1]; } LL query(LL k,LL l,LL r,LL x,LL y) { if(l>=x&&r<=y) return sum[k]; LL mid=l+r>>1,res=0; push_down(k,l,r,mid); if(x<=mid) res+=query(k<<1,l,mid,x,y); if(mid<y) res+=query(k<<1|1,mid+1,r,x,y); return res; } LL x,y,v; int main() { n=read();m=read(); for(LL i=1;i<=n;i++) a[i]=read(); build_sum(1,1,n); while(m--) { flag=read(); if(flag==1) { x=read();y=read();v=read(); change(1,1,n,x,y,v); } else { x=read();y=read(); out(query(1,1,n,x,y)),putchar(' '); } } return 0; }
三.线段树区间加法、乘法，区间求和（传送门）
思路：开两个数组，一个记录加法的lazy标记，一个记录乘法的lazy标记。标记下传时按照先乘后加的原理（有乘法标记先处理乘法标记，再处理加法标记），求和与加法没有太大的差别。
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<cstdlib> #include<iostream> #include<stack> #include<queue> #include<deque> #include<vector> #include<map> #include<set> using namespace std; #define maxn 100007 long long p; long long a[maxn]; long long sum[maxn<<2],adc[maxn<<2],adj[maxn<<2]; inline long long read() { char kr=0; char ls; for(;ls>'9'||ls<'0';kr=ls,ls=getchar()); long long xs=0; for(;ls>='0'&&ls<='9';ls=getchar()) { xs=xs*10+ls-48; } if(kr=='-') xs=0-xs; return xs; } inline void build_sum(long long k, long long l, long long r) { adc[k]=1; adj[k]=0; if(l==r) { sum[k]=a[l]; return; } long long mid=l+r>>1; if(l<=mid) build_sum(k<<1,l,mid); if(mid<r) build_sum(k<<1|1,mid+1,r); sum[k]=sum[k<<1]+sum[k<<1|1]; sum[k]%=p; } inline void push_down(long long k, long long l, long long r)//最关键的代码 { long long mid=l+r>>1; sum[k<<1]=(sum[k<<1]*adc[k]+adj[k]*(mid-l+1))%p; sum[k<<1|1]=(sum[k<<1|1]*adc[k]+adj[k]*(r-mid))%p;//维护线段树的稳定 adc[k<<1]=(adc[k<<1]*adc[k])%p; adc[k<<1|1]=(adc[k<<1|1]*adc[k])%p;//先更新乘法标记 adj[k<<1]=(adj[k<<1]*adc[k]+adj[k])%p; adj[k<<1|1]=(adj[k<<1|1]*adc[k]+adj[k])%p;//后更新加法标记 adc[k]=1;//乘法标记初始要设为1 adj[k]=0;//加法标记初始要设为0 return; } inline void ud1(long long k,long long l,long long r,long long x,long long y,long long w)//打上乘法标记 { if(y<l||r<x) return; if(x<=l&&r<=y) { sum[k]=(sum[k]*w)%p; adc[k]=(adc[k]*w)%p; adj[k]=(adj[k]*w)%p; return; } push_down(k,l,r); long long mid=l+r>>1; ud1(k<<1,l,mid,x,y,w); ud1(k<<1|1,mid+1,r,x,y,w); sum[k]=(sum[k<<1]+sum[k<<1|1])%p; } inline void ud2(long long k,long long l,long long r,long long x,long long y,long long w)//打上加法标记 { if(y<l||r<x) return; if(x<=l&&r<=y) { adj[k]=(adj[k]+w)%p; sum[k]=(sum[k]+w*(r-l+1))%p; return; } push_down(k,l,r); long long m=(l+r)/2; ud2(k<<1,l,m,x,y,w); ud2(k<<1|1, m+1,r,x,y,w); sum[k]=(sum[k<<1]+sum[k<<1|1])%p; } inline long long query(long long k,long long l,long long r,long long x,long long y) { if(y<l||r<x) return 0; if(x<=l&&r<=y) return sum[k]; push_down(k,l,r); long long mid=l+r>>1; return (query(k<<1,l,mid,x,y)+query(k<<1|1,mid+1,r,x,y))%p; } int main() { long long n, m; n=read();p=read();m=read(); for(long long i=1; i<=n; i++) { a[i]=read(); } build_sum(1, 1, n); while(m--) { long long lck; long long x,y; long long w; lck=read(); if(lck==1) { x=read();y=read();w=read(); ud1(1,1,n,x,y,w); } else if(lck==2) { x=read();y=read();w=read(); ud2(1,1,n,x,y,w); } else { x=read();y=read(); printf("%lld ", query(1,1,n,x,y)); } } return 0; }
四.线段树区间开方，区间求和（传送门）
线段树的开方操作似乎无法做到O（N）的做法，只能O（log N）暴力开方，这里有一个优化是，不论一个多大的数，在开方六次以内必然会等于 1 ，而 1 开方还是 1 ，所以可以对于线段树内的数，是 1 或 0 的打上记号，开方时直接跳过，优化常数。
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<cstdlib> #include<iostream> #include<stack> #include<queue> #include<deque> #include<vector> #include<map> #include<set> using namespace std; #define maxn 100005 long long n,m; long long a[maxn]; long long sum[maxn<<2]; bool add[maxn<<2]; long long ans=0; inline void build_sum(long long k,long long l,long long r) { if(l==r) { sum[k]=a[l]; return; } long long mid=l+r>>1; if(l<=mid) build_sum(k<<1,l,mid); if(mid<r) build_sum(k<<1|1,mid+1,r); sum[k]=sum[k<<1]+sum[k<<1|1]; add[k]=add[k<<1]&add[k<<1|1]; } inline void solve(long long k,long long l,long long r,long long x,long long y) { if(l>=x&&r<=y) { ans+=sum[k]; return; } long long mid=l+r>>1; if(x<=mid) solve(k<<1,l,mid,x,y); if(mid<y) solve(k<<1|1,mid+1,r,x,y); } inline void update(long long k,long long l,long long r,long long x,long long y) { if(add[k]) return; if(l==r) { sum[k]=sqrt(sum[k]); if(sum[k]<=1) add[k]=1; return; } long long mid=l+r>>1; if(x<=mid) update(k<<1,l,mid,x,y); if(mid<y) update(k<<1|1,mid+1,r,x,y); add[k]=add[k<<1]&add[k<<1|1]; sum[k]=sum[k<<1]+sum[k<<1|1]; } inline long long read() { char kr=0; char ls; for(;ls>'9'||ls<'0';kr=ls,ls=getchar()); long long xs=0; for(;ls>='0'&&ls<='9';ls=getchar()) { xs=xs*10+ls-48; } if(kr=='-') xs=0-xs; return xs; } int main() { n=read(); for(long long i=1;i<=n;i++) { a[i]=read(); } build_sum(1,1,n); m=read(); long long z,x,y; for(long long i=1;i<=m;i++) { z=read();x=read();y=read(); if(x>y) swap(x,y); if(z==1) { ans=0; solve(1,1,n,x,y); printf("%lld ",ans); continue; } else update(1,1,n,x,y); } return 0; }