浅入深地讲解线段树
首先是最简单的模版——区间加，区间查
我们需要这样5个函数
pushup——由下往上地传递信息
pushdown——传递懒标记
build——建立出树形结构
modify——区间加操作
query——区间查询
1.建树
struct node{
int l,r;
long long sum,add;
}tr[maxn*4];
void build(int p,int l,int r)
{
tr[p].l=l;
tr[p].r=r;
if(l==r)
{
tr[p].sum=a[l];
return ;
}
else {
int mid=(tr[p].l+tr[p].r)/2;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
pushup(p);
}
}
2.首先是pushup函数
pushup函数使用的情况是当信息被更改的时候且需要递归处理的时候使用
void pushup(int p)
{
tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;
}
3.然后是pushdown
试想一下，如果我们不使用懒标记的话，那么每一次区间的修改，我们就要暴力去修改，时间复杂度最坏的情况可以达到O(n)，我们肯定无法承受
于是懒标记就诞生了
懒标记他就是在查询的时候，如果完全包含这个区间，我们是不往下查了
反之我们在这里标记一下，add含义就是以当前节点为跟的子树中的每一个元素都加上add，注意这个add是不包
含根自己的，当我们遇到一个区间是包含的，那么我们就直接对这个区间进行操作，这样的复杂度最坏是O(logn)的
如果我们查询区间的话，我们就需要加上所有父节点的add值，我们在做查询的时候，我们用的每一个元素的值，都必须把它所有祖先的add值加上，这一步，我们可以在递归的过程中去实现
void pushdown(int p) //可以类比传消息，不断向下传递
{
if(tr[p].add){
tr[p<<1].add+=tr[p].add;
tr[p<<1].sum+=(tr[p<<1].r-tr[p<<1].l+1)*tr[p].add;
tr[p<<1|1].add+=tr[p].add;
tr[p<<1|1].sum+=(tr[p<<1|1].r-tr[p<<1|1].l+1)*tr[p].add;
tr[p].add=0;
}
}
4.modify操作
如果我们当前修改的这个区间被包含于某个节点的管辖范围，那么我们就直接更新其维护的信息，让懒标记加上更新的值
如果不能完全被包含，那么我们就递归左右子树，如果l<mid,那么说明左子树与查询的区间有交集，那么递归处理左子树，查询的范围保持不变
否则我们递归右子树
因为信息被更新了所以再最后记得pushup
void modify(int p,int l,int r,int d)
{
if(tr[p].l>=l&&tr[p].r<=r)
{
tr[p].sum+=(tr[p].r-tr[p].l+1)*d;
tr[p].add+=d;
}
else {
pushdown(p);//不能完全包含，那么每一个部分要加的值就不一样了，我们需要先传懒标记，让其懒标记的影响消失，而后再懒标记影响后的树中进行修改操作
int mid=(tr[p].l+tr[p].r)/2;
if(l<=mid)
modify(p<<1,l,r,d);
if(r>mid)
modify(p<<1|1,l,r,d);
pushup(p);
}
}
5.查询操作
同修改的操作
当完全包含的时候直接返回
否则递归处理左右自身
long long query(int p,int l,int r)
{
if(tr[p].l>=l&&tr[p].r<=r)
return tr[p].sum;
else {
pushdown(p);
int mid=(tr[p].l+tr[p].r)/2;
long long sum=0;
if(l<=mid)
sum+=query(p<<1,l,r);
if(r>mid)
sum+=query(p<<1|1,l,r);
return sum;
}
}
最简单的区间加想必大家已经理解了，那么我们来上升一个难度，讲一讲区间乘
线段树区间乘法，区间加，区间查询和
- 如果只是简单的乘法运算 那依然很简单 直接让(lazy)标记乘几就好了 后面(pushdown)的时候将乘法标记下放 然后(t[root].sum *= lazy)就好了
- 但是如果既有乘又有加呢？ 我们需要考虑是先乘还是先加 因为存在优先级这个东西（乘法比加法高 括号比乘法高）
- 所以我们将(lazy)标记改进一下 改进为记录乘法的(lazy) 和 记录加法的(add) 两个懒惰标记
- 在想要进行乘法运算的时候很简单 直接pushdown的时候(t[root].sum *= lazy)就好了 但是在进行加法运算的时候 我们需要将原来的(add * lazy) 再加上(add)
- 解释一下原因：
原来的add 是在当前操作之前进行的 所以优先级应该高于当前(add) 就像是((a[i]+5) X 4+6) 加5的操作是之前进行的 进行之后再乘4 会将之前的(+5)一起乘 而后面的+6是当前操作 因此不需要*lazy 其他操作大体和加减一样
代码
#include<bits/stdc++.h>
using namespace std;
const int N=200100;
struct node{
int l,r;
long long sum,add,mul;
}tr[N*4];
int n,mod,m;
int w[N];
void eval(node &p,int add,int mul)
{
p.add=((long long)p.add*mul+add)%mod;
p.mul=((long long)p.mul*mul)%mod;
p.sum=((long long)p.sum*mul+(long long)(p.r-p.l+1)*add)%mod;
}
void pushdown(int p)
{
eval(tr[p<<1],tr[p].add,tr[p].mul);
eval(tr[p<<1|1],tr[p].add,tr[p].mul);
tr[p].add=0;
tr[p].mul=1;
}
void pushup(int p)
{
tr[p].sum=(tr[p<<1].sum+tr[p<<1|1].sum)%mod;
}
void build(int p,int l,int r)
{
tr[p]={l,r,w[r],0,1};
if(l==r)return ;
int mid=(l+r)/2;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
pushup(p);
}
void modify(int p,int l,int r,int add,int mul)
{
if(tr[p].l>=l&&tr[p].r<=r)
{
eval(tr[p],add,mul);
return ;
}
pushdown(p);
int mid=(tr[p].l+tr[p].r)/2;
if(l<=mid)modify(p<<1,l,r,add,mul);
if(r>mid)modify(p<<1|1,l,r,add,mul);
pushup(p);
}
long long query(int p,int l,int r)
{
long long ans=0;
if(tr[p].l>=l&&tr[p].r<=r)
{
return tr[p].sum;
}
pushdown(p);
int mid=(tr[p].l+tr[p].r)/2;
if(l<=mid) ans=ans+query(p<<1,l,r)%mod;
if(r>mid)ans=ans+query(p<<1|1,l,r)%mod;
return ans;
}
int main()
{
scanf("%d%d", &n, &mod);
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
build(1, 1, n);
scanf("%d", &m);
while (m -- )
{
int t, l, r, d;
scanf("%d%d%d", &t, &l, &r);
if (t == 1)
{
scanf("%d", &d);
modify(1, l, r, 0, d);
}
else if (t == 2)
{
scanf("%d", &d);
modify(1, l, r, d, 1);
}
else printf("%d
", query(1, l, r)%mod);
}
return 0;
}
线段树区间覆盖
线段树能支持什么操作呢
区间覆盖，区间加，区间乘，区间查询，单点修改，可能远远不止这些
对区间进行操作，我们肯定要使用懒标记
那么懒标记的下放顺序就是一个问题
我们目前需要处理3个懒标记分别记为(lazy,add,mul;)
优先级应该是(lazy>mul>add)
为什么呢，首先是因为如果区间覆盖，那么前面更新的区间加，区间乘都会哑然失色，所以说区间覆盖才是巨佬，那么如果有区间覆盖的
懒标记的话，我们当然是要先下放它，并把区间加，区间乘的懒标记设为没有
按照顺序的，仿照上面的依次考虑乘法标记，和加法标记
还有一种思想是需要我们知道，就是我们的懒标记是用到，我们就(pushdown)，用不到，就让它挂着就好,如果每次修改，我们都把懒标记
全部下放一边，那和暴力没有什么差别了，懒标记也就是失去了它的意义，总归，它的作用就是，当前修改的区间用的着的，我就下放，
用不着的，就在这个节点，随着区间的更新懒标记就行
结构体
struct node{
int l,r;//控制边界
int lazy,mul,add,sum;//按照优先级的顺序进行定义
}tr[N*4];
懒标记的下放，重中之重，打起精神了
void pushdown(int p)//因为懒标记的下放是对当前节点的左右儿子产生影响的，所以只用修改左右儿子的信息，而当前点的信息除了lazy外，都不用进行修改
{
if(tr[p].lazy!=-1)
{
tr[p<<1].sum=(tr[p<<1].r-tr[p<<1].l+1)*tr[p].lazy;
tr[p<<1|1].sum=(tr[p<<1|1].r-tr[p<<1|1].l+1)*tr[p].lazy;
tr[p<<1].lazy=tr[p<<1|1].lazy=tr[p].lazy;
tr[p].lazy=-1;
}
tr[p<<1].mul*=tr[p].mul;//乘法标记
tr[p<<1|1].mul*=tr[p].mul;
tr[p<<1].sum*=tr[p].mul;//区间和直接乘上乘法标记
tr[p<<1|1].sum*=tr[p].mul;
tr[p<<1].add=tr[p<<1].add*tr[p].mul+tr[p].add;//加法标记
tr[p<<1|1].add=tr[p<<1|1].add*tr[p].mul+tr[p].add;
tr[p<<1].sum+=(tr[p<<1].r-tr[p<<1].l+1)*tr[p].add;
tr[p<<1|1].sum+=(tr[p<<1|1].r-tr[p<<1|1].l+1)*tr[p].add;
tr[p].mul=1;//乘法标记最开始也应该是为1的，表示没有
tr[p].add=0;
}
剩下的需要进行修改的部分就是在修改(update)函数里面了
void modify(int p,int l,int r,int add,int mul)
{
if(tr[p].l>=l&&tr[p].r<=r)
{
if(tr[p].lazy!=-1)
{
tr[p<<1].sum=(tr[p<<1].r-tr[p<<1].l+1)*tr[p].lazy;
tr[p<<1|1].sum=(tr[p<<1|1].r-tr[p<<1|1].l+1)*tr[p].lazy;
tr[p<<1].lazy=tr[p<<1|1].lazy=tr[p].lazy;
tr[p].lazy=-1;
return;
}
else
{
tr[p].sum=((long long)tr[p].sum*mul+(tr[p].r-tr[p].l+1)*add)%mod;
tr[p].add=((long long)tr[p].add*mul+add)%mod;
tr[p].mul=((long long)tr[p].mul*mul)%mod;
return ;
}
}
pushdown(p);
int mid=(tr[p].l+tr[p].r)/2;
if(l<=mid)modify(p<<1,l,r,add,mul);
if(r>mid) modify(p<<1|1,l,r,add,mul);
pushup(p);
}
注意：由于我们的修改函数递归进行处理的，所以程序在到达递归边界的时候，一定记得return，否则会进
入死循环
这里有一道例题，我们来看一下(CF343D Water Tree)
这道题就是让我们写出一个数据结构，使其能够满足下列操作
1.区间赋值
2.子树赋值
3.单点查询(区间会查询，单点不会查询，不丢人吗)
子树——树剖，树剖是肯定没有跑的了，前面的还是极其套路的(dfs1,dfs2,query,build)
关键就在于修改的操作，我们需要修改的部分也就是区间覆盖的懒标记出现的位置
一个在(pushdown)里面
inline void pushdown(int p)
{
if(tr[p].lazy!=-1)
{
tr[p<<1].sum=(tr[p<<1].r-tr[p<<1].l+1)*tr[p].lazy;
tr[p<<1].lazy=tr[p].lazy;
tr[p<<1|1].sum=(tr[p<<1|1].r-tr[p<<1|1].l+1)*tr[p].lazy;
tr[p<<1|1].lazy=tr[p].lazy;
tr[p].lazy=-1;
}
}
一个在(update)函数里面
inline void update(int p,int l,int r,int k)
{
if(tr[p].l>=l&&tr[p].r<=r)
{
tr[p].sum=(tr[p].r-tr[p].l+1)*k;//这个区间里面的所有数都是k了，那么区间和就是区间长度*k
tr[p].lazy=k;//标记一下，在以后更新子节点信息的时候用的着
return ;
}
pushdown(p);
int mid=(tr[p].l+tr[p].r)/2;
if(l<=mid) update(p<<1,l,r,k);
if(r>mid) update(p<<1|1,l,r,k);
pushup(p);
}
完结撒花