前言
线段树，维护区间修改的利器，种类繁多。以其码量巨大的特点骇人听闻。
(OIerhhx)为了让线段树的使用方便更加方便简洁，不再苦恼，于是写下了这篇博客。
线段树伪代码指南
这一部分主要是为了梳理线段树代码：减化码量，矫正易错。
/*important*/
线段树结构体
{
懒标记+其他信息
}
lson函数（用于遍历函数查询子区间）//简化码量
{
return (l+r)/2;
}
rson函数（用于遍历函数查询子区间）//简化码量
{
return (l+r)/2+1;
}
maketag函数(用于遍历函数修改tag)//简化码量
{
/*仅对于该修改对该节点的懒标计和其他信息*/
}
pushdown函数(用于遍历函数更新)//简化码量
{
/*用该节点tag修改子节点信息+清空tag*/
}
update函数(用于子节点回溯后更新父节点)//简化码量
{
子节点比较求值
}
建树函数
{
子区间：预处理+return
其他区间：预处理+update
}
遍历函数
{
在修改/查询区间内：修改信息（/*仅对于该修改对该节点的懒标计和其他信息*/）/统计信息+return
pushdown
与左子区间交集
递归
与右子区间交集
update
return
}
以P3372 【模板】线段树 1为例：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+100;
int n,m;
int a[N];
struct point{
int val,add,len;
}tree[N*8];
int lson(int l,int r)
{
return (l+r)/2;
}
int rson(int l,int r)
{
return (l+r)/2+1;
}
void update(int x)
{
tree[x].val=tree[x*2].val+tree[x*2+1].val;
return;
}
void pushdown(int x)
{
tree[x*2].val+=tree[x].add*tree[x*2].len;
tree[x*2+1].val+=tree[x].add*tree[x*2+1].len;
tree[x*2].add+=tree[x].add;
tree[x*2+1].add+=tree[x].add;
tree[x].add=0;
return;
}
void make(int x,int to)
{
tree[x].val+=to*tree[x].len;
tree[x].add+=to;
return;
}
void build(int l,int r,int x)
{
tree[x].len=r-l+1;
if(l==r)
{
tree[x].val=a[l];
return;
}
build(l,lson(l,r),x*2);
build(rson(l,r),r,x*2+1);
update(x);
return;
}
void ad(int l,int r,int x,int l1,int r1,int to)
{
if(l>=l1&&r<=r1)
{
make(x,to);
return;
}
pushdown(x);
if(lson(l,r)>=l1)
ad(l,lson(l,r),x*2,l1,r1,to);
if(rson(l,r)<=r1)
ad(rson(l,r),r,x*2+1,l1,r1,to);
update(x);
return;
}
int get(int l,int r,int x,int l1,int r1)
{
if(l>=l1&&r<=r1)
{
return tree[x].val;
}
pushdown(x);
int s=0;
if(lson(l,r)>=l1)
s+=get(l,lson(l,r),x*2,l1,r1);
if(rson(l,r)<=r1)
s+=get(rson(l,r),r,x*2+1,l1,r1);
update(x);
return s;
}
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
build(1,n,1);
while(m--)
{
int op;
cin>>op;
if(op==1)
{
int x,y,z;
cin>>x>>y>>z;
ad(1,n,1,x,y,z);
}
else
{
int x,y;
cin>>x>>y;
cout<<get(1,n,1,x,y)<<'n';
}
}
return 0;
}
各类线段树详解
乘加线段树
维护乘和加的线段树堪称所有线段树中最简单的一类，其关键在于线段树(tag)维护的顺序，我们采用先乘再加的形式。
原因在于用一个已经乘过的加(tag)，先加值，就没有办法再乘一次了。
以下是乘加线段树的模板：
P3373 【模板】线段树 2
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+100;
int n,m,p;
struct point{
int val,add,mul,len;
}tree[N*8];
int a[N];
inline int lson(int l,int r)
{
return (l+r)/2;
}
inline int rson(int l,int r)
{
return (l+r)/2+1;
}
inline void update(int x)
{
tree[x].val=(tree[x*2].val+tree[x*2+1].val)%p;
return;
}
inline void make1(int x,int to)
{
tree[x].add=(tree[x].add+to)%p;
tree[x].val=(tree[x].val+to*tree[x].len)%p;
return;
}
inline void make2(int x,int to)
{
tree[x].add=(tree[x].add*to)%p;
tree[x].mul=(tree[x].mul*to)%p;
tree[x].val=(tree[x].val*to)%p;
return;
}
inline void pushdown(int x)
{
tree[x*2].val=(tree[x].mul*tree[x*2].val+(tree[x*2].len*tree[x].add)%p)%p;
tree[x*2+1].val=(tree[x].mul*tree[x*2+1].val+(tree[x*2+1].len*tree[x].add)%p)%p;
tree[x*2].mul=(tree[x*2].mul*tree[x].mul)%p;
tree[x*2+1].mul=(tree[x*2+1].mul*tree[x].mul)%p;
tree[x*2].add=(tree[x*2].add*tree[x].mul+tree[x].add)%p;
tree[x*2+1].add=(tree[x*2+1].add*tree[x].mul+tree[x].add)%p;
tree[x].add=0;
tree[x].mul=1;
return;
}
inline void build(int l,int r,int x)
{
tree[x].len=r-l+1;
tree[x].mul=1;
if(l==r)
{
tree[x].val=a[l]%p;
return;
}
build(l,lson(l,r),x*2);
build(rson(l,r),r,x*2+1);
update(x);
return;
}
inline void ad(int l,int r,int x,int l1,int r1,int to)
{
if(l1<=l&&r1>=r)
{
make1(x,to);
return;
}
pushdown(x);
if(l1<=lson(l,r))
ad(l,lson(l,r),x*2,l1,r1,to);
if(r1>=rson(l,r))
ad(rson(l,r),r,x*2+1,l1,r1,to);
update(x);
return;
}
inline void mu(int l,int r,int x,int l1,int r1,int to)
{
if(l1<=l&&r1>=r)
{
make2(x,to);
return;
}
pushdown(x);
if(l1<=lson(l,r))
mu(l,lson(l,r),x*2,l1,r1,to);
if(r1>=rson(l,r))
mu(rson(l,r),r,x*2+1,l1,r1,to);
update(x);
return;
}
inline int get(int l,int r,int x,int l1,int r1)
{
if(l1<=l&&r1>=r)
{
return tree[x].val;
}
pushdown(x);
int sum=0;
if(l1<=lson(l,r))
sum=(sum+get(l,lson(l,r),x*2,l1,r1))%p;
if(r1>=rson(l,r))
sum=(sum+get(rson(l,r),r,x*2+1,l1,r1))%p;
update(x);
return sum;
}
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>p;
for(int i=1;i<=n;i++)
cin>>a[i];
build(1,n,1);
while(m--)
{
int op;
cin>>op;
if(op==1)
{
int x,y,z;
cin>>x>>y>>z;
mu(1,n,1,x,y,z);
}
if(op==2)
{
int x,y,z;
cin>>x>>y>>z;
ad(1,n,1,x,y,z);
}
if(op==3)
{
int x,y;
cin>>x>>y;
cout<<get(1,n,1,x,y)<<'n';
}
}
return 0;
}
最值线段树
最值线段树顾名思义，维护的是区间最值，更新方法于乘加线段树很类似，就不赘述了。
值得注意的是，加乘(tag)往往与赋值(tag)冲突，需要额外处理，例如将加乘操作只更新赋值(tag)，不更新加乘(tag)等。
以下是最值线段树的模板：
P1253 [yLOI2018] 扶苏的问题
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+100;
int n,q;
int a[N];
struct point{
int tag1,tag2,val;
}tree[N*8];
int lson(int l,int r)
{
return (l+r)/2;
}
int rson(int l,int r)
{
return (l+r)/2+1;
}
void update(int x)
{
tree[x].val=max(tree[x*2].val,tree[x*2+1].val);
return;
}
void maketag1(int x,int to)
{
tree[x].tag1=to;
tree[x].tag2=0;
tree[x].val=to;
return;
}
void maketag2(int x,int to)
{
if(tree[x].tag1==LLONG_MIN)
tree[x].tag2+=to;
else
tree[x].tag1+=to;
tree[x].val+=to;
return;
}
void pushdown(int x)
{
if(tree[x].tag1!=LLONG_MIN)
{
maketag1(x*2,tree[x].tag1);
maketag1(x*2+1,tree[x].tag1);
}
maketag2(x*2,tree[x].tag2);
maketag2(x*2+1,tree[x].tag2);
tree[x].tag1=LLONG_MIN;
tree[x].tag2=0;
return;
}
void build(int l,int r,int x)
{
tree[x].tag1=LLONG_MIN;
if(l==r)
{
tree[x].val=a[l];
return;
}
build(l,lson(l,r),x*2);
build(rson(l,r),r,x*2+1);
update(x);
return;
}
void change1(int l,int r,int x,int l1,int r1,int to)
{
if(l>=l1&&r<=r1)
{
maketag1(x,to);
return;
}
pushdown(x);
if(lson(l,r)>=l1)
change1(l,lson(l,r),x*2,l1,r1,to);
if(rson(l,r)<=r1)
change1(rson(l,r),r,x*2+1,l1,r1,to);
update(x);
return;
}
void change2(int l,int r,int x,int l1,int r1,int to)
{
if(l>=l1&&r<=r1)
{
maketag2(x,to);
return;
}
pushdown(x);
if(lson(l,r)>=l1)
change2(l,lson(l,r),x*2,l1,r1,to);
if(rson(l,r)<=r1)
change2(rson(l,r),r,x*2+1,l1,r1,to);
update(x);
return;
}
int get(int l,int r,int x,int l1,int r1)
{
if(l>=l1&&r<=r1)
{
return tree[x].val;
}
int sum=LLONG_MIN;
pushdown(x);
if(lson(l,r)>=l1)
sum=max(sum,get(l,lson(l,r),x*2,l1,r1));
if(rson(l,r)<=r1)
sum=max(sum,get(rson(l,r),r,x*2+1,l1,r1));
update(x);
return sum;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++)
cin>>a[i];
build(1,n,1);
while(q--)
{
int op;
cin>>op;
if(op==1)
{
int l,r,x;
cin>>l>>r>>x;
change1(1,n,1,l,r,x);
}
if(op==2)
{
int l,r,x;
cin>>l>>r>>x;
change2(1,n,1,l,r,x);
}
if(op==3)
{
int l,r;
cin>>l>>r;
cout<<get(1,n,1,l,r)<<'n';
}
}
return 0;
}
区间前后缀线段树
区间前后缀线段树，较前两种少见很多。他更为灵活，并且可以解决很多抽象的问题，例如：最大字段和，最长相间(01)串等等，也算是出正解、考场得分的利器。但同样的，他的难度也相较更大。
我们选择其中较为灵活的一种来讲解：最长相间(01)串。其余的均可以通过他类比。
以下是最长相间(01)串的模板：
P6492 [COCI2010-2011#6] STEP
区间前后缀线段树，所维护的不再是简单的(tag)而是多变的更新操作。
我们人为的将区间分成了子段，因此除了单个子区间的贡献((1))，还要考虑子区间因更新操作所带来的合并与分裂的贡献((2))。
我们分别讨论这两种贡献：
((1)):
在这种情况中，不涉及区间的合并与分裂操作。
我们只简单讨论整个子段的贡献，与普通线段树无异。
因此我们维护区间总贡献即可。
((2))
我们考虑简化操作。
对于维护时，我们人为将所有区间拆开，这样我们就只用考虑合并的贡献，而不用考虑分裂的贡献了。
对于合并，我们延断点向两边扩展，根据贪心的思想，我们希望两边延伸出的部分，贡献都尽量大，即左区间后缀和右区间前缀的贡献尽量大。因此我们维护区间前缀和后缀的最值即可解决情况((2))的问题。
问题来了，怎么维护前缀和后缀呢？
我们考虑一个区间在大多数情况下的最大前缀都是左子区间的最大前缀，但不排除有特殊情况：这个区间的前缀比左子区间本身更大，显然，我们特判一下，加上右子区间的最大前缀即可。后缀同理。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+100;
int n,q;
int a[N];
struct point{
int lsum,rsum,len,sum;
}tree[N*8];
int lson(int l,int r)
{
return (l+r)/2;
}
int rson(int l,int r)
{
return (l+r)/2+1;
}
void build(int l,int r,int x)
{
tree[x].len=r-l+1;
tree[x].lsum=1;
tree[x].rsum=1;
tree[x].sum=1;
if(l==r)
return;
build(l,lson(l,r),x*2);
build(rson(l,r),r,x*2+1);
return;
}
void update(int x,int l,int r)
{
tree[x].sum=max(tree[x*2].sum,tree[x*2+1].sum);
tree[x].lsum=tree[x*2].lsum;
tree[x].rsum=tree[x*2+1].rsum;
if(a[lson(l,r)]!=a[rson(l,r)])
{
tree[x].sum=max(tree[x].sum,tree[x*2].rsum+tree[x*2+1].lsum);
if(tree[x].lsum==tree[x*2].len)
tree[x].lsum+=tree[x*2+1].lsum;
if(tree[x].rsum==tree[x*2+1].len)
tree[x].rsum+=tree[x*2].rsum;
}
return;
}
void change(int l,int r,int x,int to)
{
if(l==r)
{
a[to]^=1;
return;
}
if(lson(l,r)>=to)
change(l,lson(l,r),x*2,to);
if(rson(l,r)<=to)
change(rson(l,r),r,x*2+1,to);
update(x,l,r);
return;
}
int query()
{
return tree[1].sum;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>q;
build(1,n,1);
while(q--)
{
int x;
cin>>x;
change(1,n,1,x);
cout<<query()<<'n';
}
return 0;
}
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
