线段树合集整理"/>
线段树合集整理
-
前言
本章不是线段树教程，包含内容是博主自己刷题时的整理，请不要转载
训练地址：一本通线段树地址 （剩余在每个板块都有链接
-
单点修改，区间查询
没什么好说的，注意每次修改要记得pushup
附板子，0为单点修改，1为查询区间和
一般这样还是搞树状数组吧 这破玩意常数太大卡死了
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<iomanip>
using namespace std;
#define int long long
inline int read()
{int x=0,y=1; char c=getchar();while(c<'0'||c>'9') {if(c=='-') y=-1; c=getchar();}while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();return x*y;
}
const int maxn=100005;
int n,m;
int tree[maxn*4];
void push_up(int id)
{tree[id]=tree[id<<1]+tree[id<<1|1];return ;
}
void modify(int id,int l,int r,int pos,int x)
{if(l==r) {tree[id]+=x; return ;}int mid=(l+r)>>1;if(pos<=mid) modify(id<<1,l,mid,pos,x);else modify(id<<1|1,mid+1,r,pos,x);push_up(id);return ;
}
int query(int id,int l,int r,int x,int y)
{if(l>=x&&r<=y) return tree[id];int ans=0;int mid=(l+r)>>1;if(x<=mid) ans+=query(id<<1,l,mid,x,y);if(y>mid) ans+=query(id<<1|1,mid+1,r,x,y);return ans;
}
signed main()
{n=read(); m=read();while(m--){int op=read();int l=read(),r=read();if(!op) modify(1,1,n,l,r);else printf("%lld\n",query(1,1,n,l,r));}return 0;
}-
区间修改，区间查询
也是线段树基操， 附板子，C是修改区间，Q是查询
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<string>
#include<queue>
#include<iomanip>
using namespace std;
const int maxn=100005;
#define int long long
inline int read()
{int x=0,y=1; char c=getchar();while(c<'0'||c>'9') {if(c=='-') y=-1; c=getchar();}while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();return x*y;
}
int n,Q;
int a[maxn],tree[maxn*4];
int tag[maxn*4];
char op[2];
void push_up(int id)
{tree[id]=tree[id<<1]+tree[id<<1|1];return ;
}
void Add(int id,int l,int r,int val)
{tag[id]+=val;tree[id]+=(r-l+1)*val;return ;
}
void build(int id,int l,int r)
{if(l==r) {tree[id]=a[l]; return ;}int mid=(l+r)>>1;build(id<<1,l,mid);build(id<<1|1,mid+1,r);push_up(id);return ;
}
void push_down(int id,int l,int r)
{if(!tag[id]) return ;int mid=(l+r)>>1;Add(id<<1,l,mid,tag[id]);Add(id<<1|1,mid+1,r,tag[id]);tag[id]=0;return ;
}
void modify(int id,int l,int r,int x,int y,int val)
{if(x<=l&&r<=y){Add(id,l,r,val);return ;}int mid=(l+r)>>1;push_down(id,l,r);if(x<=mid) modify(id<<1,l,mid,x,y,val);if(y>mid) modify(id<<1|1,mid+1,r,x,y,val);push_up(id);return ;
}
int query(int id,int l,int r,int x,int y)
{if(x<=l&&r<=y) return tree[id];int ans=0;push_down(id,l,r);int mid=(l+r)>>1;if(x<=mid) ans+=query(id<<1,l,mid,x,y);if(y>mid) ans+=query(id<<1|1,mid+1,r,x,y);return ans;
}
signed main()
{n=read(); Q=read();for(int i=1;i<=n;++i) a[i]=read();build(1,1,n);while(Q--){scanf("%s",op);int a,b,c;if(op[0]=='C'){a=read(); b=read();c=read();modify(1,1,n,a,b,c);}else {a=read(); b=read();printf("%lld\n",query(1,1,n,a,b));}}return 0;
}-
区间最大值
含金量不高，但有变形 可以考虑转化，每次加一个数，即使假设全部是添加数，一共有T个，开个T长度的线段树，搞个计数器，那么每次就在那个位置单点修改，区间查询即可
具体看实现：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<iomanip>
#include<queue>
using namespace std;
const int maxn=200005;
const int inf=0x80000000;
inline int read()
{int x=0,y=1; char c=getchar();while(c<'0'||c>'9') {if(c=='-') y=-1; c=getchar();}while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();return x*y;
}
int T,mod,n,cnt(0);
int tree[maxn*4];
char op[2];
void push_up(int id)
{tree[id]=max(tree[id<<1],tree[id<<1|1]);return ;
}
void build(int id,int l,int r)
{if(l==r) {tree[id]=0; return ;}int mid=(l+r)>>1;build(id<<1,l,mid);build(id<<1|1,mid+1,r);push_up(id);return ;
}
void modify(int id,int l,int r,int pos,int val)
{if(l==r) {tree[id]=val; return ;}int mid=(l+r)>>1;if(pos<=mid) modify(id<<1,l,mid,pos,val);else modify(id<<1|1,mid+1,r,pos,val);push_up(id);return ;
}
int query(int id,int l,int r,int x,int y)
{if(x<=l&&r<=y) return tree[id];int ans=inf;int mid=(l+r)>>1;if(x<=mid) ans=max(query(id<<1,l,mid,x,y),ans);if(y>mid) ans=max(ans,query(id<<1|1,mid+1,r,x,y));return ans;
}
int pre(0);
int main()
{T=read(); mod=read();n=T; build(1,1,n);while(T--){scanf("%s",op);if(op[0]=='A'){++cnt;int val=read();modify(1,1,n,cnt,(pre+val)%mod);}else{int x=read();printf("%d\n",pre=query(1,1,n,cnt-x+1,cnt));}}return 0;
}-
区间开根号
bzoj3211原题。
属于线段树变形题，花仔很有趣♂
首先我们举个栗子，即使是1e7~1e8范围内的数，在不断开平方下取整的过程中逐渐趋近于，这时再开方仍时原数，可以进行剪枝，因此实际操作次数应该在5+次左右（1e9嘛
所以区间修改时先单点搞，复杂度不会爆，（头一次看见退化的区间修改笑死
#include<iostream>
#include<cstdio>
#include<string>
#include<cmath>
#include<string>
#include<iomanip>
#include<queue>
using namespace std;
const int maxn=100005;
typedef long long ll;
inline int read()
{int x=0,y=1; char c=getchar();while(c<'0'||c>'9') {if(c=='-') y=-1; c=getchar();}while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();return x*y;
}
int n,a[maxn],m;
struct node
{ll sum,mx;
}tree[maxn*4];
void push_up(int id)
{tree[id].sum=tree[id<<1].sum+tree[id<<1|1].sum;tree[id].mx=max(tree[id<<1].mx,tree[id<<1|1].mx);return ;
}
void build(int id,int l,int r)
{if(l==r){tree[id].sum=a[l];tree[id].mx=tree[id].sum;return ;}int mid=(l+r)>>1;build(id<<1,l,mid);build(id<<1|1,mid+1,r);push_up(id);return ;
}
void modify(int id,int l,int r,int x,int y)
{if(tree[id].mx==1||tree[id].mx==0) return ;if(l==r){tree[id].sum=(ll)floor(sqrt(tree[id].mx));tree[id].mx=tree[id].sum;return ;}int mid=(l+r)>>1;if(x<=mid) modify(id<<1,l,mid,x,y);if(y>mid) modify(id<<1|1,mid+1,r,x,y);push_up(id);return ;
}
ll query(int id,int l,int r,int x,int y)
{if(x<=l&&r<=y) return tree[id].sum;int mid=(l+r)>>1;ll ans=0;if(x<=mid) ans+=query(id<<1,l,mid,x,y);if(y>mid) ans+=query(id<<1|1,mid+1,r,x,y);return ans;
}
int main()
{n=read();for(int i=1;i<=n;i++) a[i]=read();build(1,1,n);m=read();while(m--){int x,l,r;x=read(); l=read(); r=read();if(x==2) modify(1,1,n,l,r);else printf("%lld\n",query(1,1,n,l,r));}return 0;
} -
区间取模和区间查询
CF438D The Child and Sequence://www.luogu/problem/CF438D
这一题可以类比上一个区间开根号，主题思想是个优化的暴力
先提出个结论的进行次数只有log次
证明显然，，只有p取m/2下取整时，得数最大
因此我们只要看一个区间什么时候不需要再进行取模，即区间最大值小于模数时，直接跳过
上代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<vector>
#include<cstdlib>
#include<queue>
using namespace std;
#define int long long
const int maxn=1e5+5;
#define lc(x) x<<1
#define rc(x) x<<1|1
#define sum(x) tree[x].sum
#define mx(x) tree[x].mx
struct seg_tree
{int sum,mx;
}tree[maxn<<2];
inline int read()
{int x=0,y=1; char c=getchar();while(c<'0'||c>'9') {if(c=='-') y=-1; c=getchar();}while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); return x*y;
}
int n,m;
int val[maxn];
void push_up(int id)
{sum(id)=sum(lc(id))+sum(rc(id));mx(id)=max(mx(lc(id)),mx(rc(id)));return ;
}
void build(int id,int l,int r)
{if(l==r) {mx(id)=sum(id)=val[l]; return ;}int mid=(l+r)>>1;build(lc(id),l,mid);build(rc(id),mid+1,r);push_up(id);return ;
}
int query(int id,int l,int r,int x,int y)
{if(x<=l&&r<=y) return sum(id);int mid=(l+r)>>1;int ans=0;if(x<=mid) ans+=query(lc(id),l,mid,x,y);if(y>mid) ans+=query(rc(id),mid+1,r,x,y);return ans;
}
void modify(int id,int l,int r,int x,int y,int p)
{if(mx(id)<p) return ;if(l==r) {sum(id)%=p; mx(id)%=p; return ;}int mid=(l+r)>>1;if(x<=mid) modify(lc(id),l,mid,x,y,p);if(y>mid) modify(rc(id),mid+1,r,x,y,p);push_up(id);return ;
}
void update(int id,int l,int r,int pos,int val)
{if(l==r) {sum(id)=mx(id)=val; return ;}int mid=(l+r)>>1;if(pos<=mid) update(lc(id),l,mid,pos,val);else update(rc(id),mid+1,r,pos,val);push_up(id);return ;
}
signed main()
{n=read(); m=read();for(int i=1;i<=n;i++) val[i]=read();build(1,1,n);while(m--){int opt,l,r,x;opt=read(); l=read(); r=read();if(opt==1) printf("%lld\n",query(1,1,n,l,r));else if(opt==2){x=read(); modify(1,1,n,l,r,x);}else update(1,1,n,l,r);}return 0;
} -
区间乘法&区间加法
有几点需要注意：
- 乘法的优先级高于加法，因此优先处理乘法的懒标
- 注意 乘法和加法懒标要记得每个点都初始化，乘法tag=1；加法tag=0
- 操作过程中，不论标记是否为0我们都要下传！尤其是乘法，可能导致直接挂一半分
- 局部long long即可
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<iomanip>
#include<cstdlib>
using namespace std;
typedef long long ll;
#define fabs(x) x>0?x:-x
#define register reg
inline int read()
{int x=0,y=1; char c=getchar();while(c<'0'||c>'9') {if(c=='-') y=-1; c=getchar();}while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();return x*y;
}
const int maxn=100005;
int p;
ll tree[maxn*4];
int n,m;
ll a[maxn];
struct node
{ll mul,pul;
}tag[maxn*4];
void push_up(int id)
{tree[id]=(ll)(tree[id<<1]+tree[id<<1|1])%p;return ;
}
void build(int id,int l,int r)
{tag[id].mul=1;tag[id].pul=0;if(l==r){tree[id]=(ll)a[l]%p;return ;}int mid=(l+r)>>1;build(id<<1,l,mid);build(id<<1|1,mid+1,r);push_up(id);return ;
}
inline void Add(int id,int l,int r,ll pls,ll mls)
{tag[id].mul=(ll)(tag[id].mul*mls)%p;tag[id].pul=(ll)(tag[id].pul*mls)%p;tree[id]=(ll)(tree[id]*mls)%p;tag[id].pul=(ll)(tag[id].pul+pls)%p;tree[id]=(ll)(tree[id]+(r-l+1)*pls%p)%p;return ;
}
void push_down(int id,int l,int r)
{int mid=(l+r)>>1;Add(id<<1,l,mid,tag[id].pul,tag[id].mul);Add(id<<1|1,mid+1,r,tag[id].pul,tag[id].mul);tag[id].mul=1; tag[id].pul=0;return ;
}
void modify_mult(int id,int l,int r,int x,int y,ll val)
{//cout<<"l: "<<l<<" "<<"r: "<<r<<endl;if(x<=l&&r<=y) {Add(id,l,r,0,val); return ;}push_down(id,l,r);int mid=(l+r)>>1;if(x<=mid) modify_mult(id<<1,l,mid,x,y,val);if(y>mid) modify_mult(id<<1|1,mid+1,r,x,y,val);push_up(id);return ;
}
void modify_add(int id,int l,int r,int x,int y,ll val)
{if(x<=l&&r<=y) {Add(id,l,r,val,1); return ;}push_down(id,l,r);int mid=(l+r)>>1;if(x<=mid) modify_add(id<<1,l,mid,x,y,val);if(y>mid) modify_add(id<<1|1,mid+1,r,x,y,val);push_up(id);return ;
}
ll query(int id,int l,int r,int x,int y)
{if(x<=l&&r<=y) return tree[id]%p;int mid=(l+r)>>1; ll ans(0);push_down(id,l,r);if(x<=mid) ans+=query(id<<1,l,mid,x,y)%p;if(y>mid) ans+=query(id<<1|1,mid+1,r,x,y)%p;return ans%p;
}
int main()
{n=read(); p=read();for(int i=1;i<=n;i++) scanf("%lld",&a[i]);build(1,1,n);m=read();while(m--){int opt=read();if(opt==1){int l,r; ll val;l=read(); r=read(); scanf("%lld",&val);modify_mult(1,1,n,l,r,val%p);}else if(opt==2){int l,r; ll val;l=read(); r=read(); scanf("%lld",&val);modify_add(1,1,n,l,r,val%p);}else{int l,r; l=read(); r=read();printf("%lld\n",query(1,1,n,l,r));}}return 0;
}-
区间合并类线段树
最好的例子就是这道题
简要题意就是求区间最大子段和，外加单点修改
重点就在如何维护区间上传的信息维护，这里需要四个参数，区间所有元素和，区间最大子段和，以左端元素为左端点的最大区间和，以右端元素为右端点的最大区间和
合并时考虑最大子段和是否超过区间位置，因此分两种大情况考虑
注意区间合并时的情况讨论
注意这里：坑点；答案如果覆盖区间的左右段，需要再合并一次，合并操作同pushup操作
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
using namespace std;
const int maxn=500005;
const int min_inf=0x80000000;
#define int long long
inline int read()
{int x=0,y=1; char c=getchar();while(c<'0'||c>'9') {if(c=='-') y=-1; c=getchar();}while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();return x*y;
}
int n,a[maxn],m;
struct node
{int sum,dat; //dat最大子段和int lmax,rmax;
}tree[maxn*4];
void push_up(int id)
{int lc=id<<1,rc=id<<1|1;tree[id].sum=tree[lc].sum+tree[rc].sum;tree[id].lmax=max(tree[lc].lmax,tree[lc].sum+tree[rc].lmax);tree[id].rmax=max(tree[rc].rmax,tree[rc].sum+tree[lc].rmax);tree[id].dat=max(tree[lc].dat,tree[rc].dat);tree[id].dat=max(tree[id].dat,tree[lc].rmax+tree[rc].lmax);return ;
}
void build(int id,int l,int r)
{if(l==r){tree[id].sum=a[l];tree[id].dat=tree[id].sum;tree[id].rmax=tree[id].lmax=tree[id].sum;return ;}int mid=(l+r)>>1;build(id<<1,l,mid);build(id<<1|1,mid+1,r);push_up(id);return ;
}
void modify(int id,int l,int r,int pos,int x)
{if(l==r){tree[id].sum=x;tree[id].dat=tree[id].rmax=tree[id].lmax=x;return ;}int mid=(l+r)>>1;if(pos<=mid) modify(id<<1,l,mid,pos,x);else modify(id<<1|1,mid+1,r,pos,x);push_up(id);return ;
}
node query(int id,int l,int r,int x,int y)
{if(x<=l&&r<=y) return tree[id];int mid=(l+r)>>1;node ans,ta,tb;if(y<=mid) return query(id<<1,l,mid,x,y);if(x>mid) return query(id<<1|1,mid+1,r,x,y);ta=query(id<<1,l,mid,x,y); tb=query(id<<1|1,mid+1,r,x,y);ans.sum=ta.sum+tb.sum;ans.lmax=max(ta.lmax,ta.sum+tb.lmax);ans.rmax=max(tb.rmax,tb.sum+ta.rmax);ans.dat=max(max(ta.dat,tb.dat),ta.rmax+tb.lmax);return ans;
}
signed main()
{n=read(); m=read();for(int i=1;i<=n;i++) a[i]=read();build(1,1,n);while(m--){int opt,x,y;opt=read(); x=read(); y=read();if(opt==2) modify(1,1,n,x,y);else {if(x>y) swap(x,y); printf("%lld\n",query(1,1,n,x,y).dat);}}return 0;
}-
区间gcd和区间修改
一道例题：interval GCD
膜你赛曾经打过原题，还写过题解 自卖自夸
就两个要点：
- 根据《九章算术》之更相减损术
二死了，，它扩展到多个数同时相减，这就构成了差分 - 因此构造差分序列，维护区间加只需要线段树两个单点修改，维护区间的左端点只需要用树状数组维护原差分序列，就van♂事了
代码没啥，相信各位都能手撕+吊打：
#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<iomanip>
using namespace std;
const int maxn=500005;
#define fabs(x) x>0?x:-x
//typedef long long ll;
#define int long long
inline int read()
{int x=0,y=1; char c=getchar();while(c<'0'||c>'9') {if(c=='-') y=-1; c=getchar();}while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();return x*y;
}
int n,a[maxn];
int m;
int gcd(int a,int b)
{if(!b) return a;return gcd(b,a%b);
}
struct BITtree
{int c[maxn];int lowbit(int x) {return x&(-x);}void add(int now,int x){for(;now<=n;now+=lowbit(now)) c[now]+=x;return ;}int query(int now){int sum=0;for(;now;now-=lowbit(now)) sum+=c[now];return sum;}
}bit;
int tree[maxn*4];
void pushup(int id)
{tree[id]=gcd(tree[id<<1],tree[id<<1|1]);return ;
}
void build(int id,int l,int r)
{if(l==r){tree[id]=a[l]-a[l-1];return ;}int mid=(l+r)>>1;build(id<<1,l,mid);build(id<<1|1,mid+1,r);pushup(id);return ;
}
void modify(int id,int l,int r,int pos,int val)
{if(l==r){tree[id]+=val;return ;}int mid=(l+r)>>1;if(pos<=mid) modify(id<<1,l,mid,pos,val);else m更多推荐
线段树合集整理
发布评论