线段树标记永久化 学习笔记【线段树】
点击量:455
尽管还没有接触到主席树的区间修改或其它可持久化结构,但是标记永久化这个东西在线段树上并不是一个鸡肋的东西,用在以常数大著称的线段树上可以有效地打分块的脸优化下放lazytag带来的较大常数。
我们知道,普通的线段树中,碰到lazytag就要pushdown,这样才能保证下面子树权值的正确性。但是pushdown的常数较大,它要下方lazytag,修改权值,并把自己身上的lazytag删去。在修改操作较多的题目中,劣势较为明显。
有一种叫做标记永久化的lazytag,它可以不用pushdown,也就是在哪里加的lazytag,它就一直待在哪里。其实标记永久化的思想还是比较好理解的,当查询碰到lazytag时,就把答案加上要查询的区间长度乘上lazytag,其实和lazytag的下放修改效果差不多,但是显著减小了常数。
因为在树套树、主席树以及很多可持久化结构中,子树多而杂,下放lazytag是很麻烦的,这时就不得不用到标记永久化,也就是在一步一步访问下去的时候,会先访问到上面的信息,一边处理一边进入子树,这样就达到了和“下放lazytag一样的效果”。
总之,在可以很多线段树中,都可以用到标记永久化的技巧。它可以帮助我们优化常数,使结构简洁并减少码长。对以后的扩展学习可能有帮助。因此在写线段树的时候要多加尝试练习。
效果图
Code:
#include<cstdio>
#include<cstring>
#define ls (k<<1)
#define rs (k<<1|1)
#define mid (l+r>>1)
#define Mid (t[k].l+t[k].r>>1)
struct node
{
int l,r;
long long lazy,v;
node(int l,int r)
{
this->l=l;
this->r=r;
lazy=0;
v=0;
}
node(){}
}t[400000];
long long a[100100];
void build(int k,int l,int r)
{
t[k]=node(l,r);
if(l==r)
{
t[k].v=a[l];
return;
}
build(ls,l,mid);
build(rs,mid+1,r);
t[k].v=t[ls].v+t[rs].v;
}
void change(int k,int l,int r,long long x)
{
t[k].v+=x*(r-l+1);
if(t[k].l==l&&t[k].r==r)
{
t[k].lazy+=x;
return;
}
if(r<=Mid)
return change(ls,l,r,x);
if(l>Mid)
return change(rs,l,r,x);
change(ls,l,Mid,x);
change(rs,Mid+1,r,x);
}
long long ask(int k,int l,int r)
{
if(t[k].l==l&&t[k].r==r)
return t[k].v;
if(r<=Mid)
return t[k].lazy*(r-l+1)+ask(ls,l,r);
if(l>Mid)
return t[k].lazy*(r-l+1)+ask(rs,l,r);
return t[k].lazy*(r-l+1)+ask(ls,l,Mid)+ask(rs,Mid+1,r);
}
int main()
{
int n,m,op,u,v;
long long w;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%lld\n",&a[i]);
build(1,1,n);
for(int i=1;i<=m;++i)
{
scanf("%d",&op);
if(op==1)
{
scanf("%d%d%lld",&u,&v,&w);
change(1,u,v,w);
}
else
{
scanf("%d%d",&u,&v);
printf("%lld\n",ask(1,u,v));
}
}
return 0;
}
[…] 【线段树标记永久化学习笔记】小知识点 […]
… [Trackback]
[…] There you will find 3645 additional Information to that Topic: wjyyy.top/1441.html […]