线段树标记永久化 学习笔记【线段树】

作者: wjyyy 分类: 学习笔记,线段树 发布时间: 2018-08-28 20:27

点击量:29

 

    尽管还没有接触到主席树的区间修改或其它可持久化结构,但是标记永久化这个东西在线段树上并不是一个鸡肋的东西,用在以常数大著称的线段树上可以有效地打分块的脸优化下放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;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */