首页 > 代码库 > Pascal 线段树 lazy-tag 模板

Pascal 线段树 lazy-tag 模板

 先说下我的代码风格(很丑,勿喷)

    maxn表示最大空间的四倍

    tree数组表示求和的线段树

    delta表示增减的增量标记

    sign表示覆盖的标记

    delta,sign实际上都是lazy标志

    pushdown表示标记下传

    pushup表示标记上传(即求和,区间最值)

    update表示数据更新

       线段树(segment tree)是一种特别有用的数据结构,我们在维护区间各种信息的时候它就是利器。可能读者嫌线段树代码太长,不想写,而树状数组代码简洁易于便携,但是我在这里想说,线段树能做到的很多东西树状数组无法做到,而若掌握了线段树的基本框架,再去写熟练的话,基本上能够做到较短的时间内DEBUG完。

      我们来介绍一下什么是线段树。

      问题1:

    我们拥有一个数列,需要维护三个操作

                       1.单点修改,把a[i]的值改成v

                       2.区间修改,把a[i]~a[j]的值改成v

        3.区间求和,求出a[i]~a[j]的和

      我们不难想到使用数组存储这些东西,对于每个询问我们暴力修改,可这样的话,对于每一段区间,我们需要耗费的时间是r-l+1,当Q特别大、或者区间长度特别大的时候,时间无法忍受。这时候线段树的应用便出来了。

  何谓线段树?我们把线段存储在树形结构中,利用树形结构维护线段信息的数据结构,就是线段树。

  我们利用二分建树,建立一颗二叉树。为什么是二叉树呢?我个人理解是,这方便我们二分查找,二分递归,大大减少编程复杂度

  而,我们每次需要的线段信息,只需要在线段树中检索, 线段树的实质是,一颗存储着线段信息的二叉搜索树。

       我们把一个长的线段(区间),不断的二分划分,即[a,b]划分成[a,(a+b)>>1](leftchild),[(a+b)>>1+1,b](rightchild); 直到a=b为止。

       我们把a=b的这个线段称为叶子节点。在某些题内,叶子节点存储的就是该点在线性结构所对应的信息。

  由上可知,我们不断划分着[a,b]那么对于每一个[a,(a+b)>>1],[(a+b)>>1+1,b]它的左儿子和右儿子也是满足"线段树"性质

  

         上图是我们划分[1,10]区间的过程。现在我们回到问题1

         我们发现如果是一个一个叶子结点访问,那么每次访问的时间甚至比O(n)的数组模拟要长。

    那么我们再看一个简单版的问题1

            问题2:

      给定一个序列

      1.修改其中一个点

        Sub:单点减小某值

        Add:单点增加某值

      2.询问区间和

        Query:询问区间和

    

   现在我们可以通过每次查找到叶子节点,暴力修改。

        然后再递归求解区间和。

   具体代码如下:   

  

const maxn=300001;var tree:packed array [0..maxn] of longint;procedure pushup(now:longint);begin  tree[now]:=tree[now<<1]+tree[now<<1+1]; //区间求和end;procedure build(l,r,now:longint);var mid:longint;begin  if l=r then     begin       read(tree[now]); //到叶子节点时输入信息并退出       exit;     end;  mid:=(l+r) shr 1;  build(l,mid,now<<1);  build(mid+1,r,now<<1+1);  pushup(now);end;procedure update(p,add,l,r,now:longint); //更新数据var mid:longint;begin  if l=r then    begin      inc(tree[now],add);      exit;    end;  mid:=(l+r) shr 1;  if p<=mid then update(p,add,l,mid,now<<1) //递归求解  else update(p,add,mid+1,r,now<<1+1);  pushup(now);end;function query(left,right,l,r,now:longint):longint; //询问和var mid,ans:longint;begin  if (left<=l) and (r<=right) then exit(tree[now]);  mid:=(l+r) shr 1;  ans:=0;  if left<=mid then inc(ans,query(left,right,l,mid,now<<1));  if right>mid then inc(ans,query(left,right,mid+1,r,now<<1+1));  exit(ans);end;procedure ques(n:longint);var ch:char; a,b:longint;  temp:string;begin  while true do    begin      temp:=‘‘;      ch:=1;        while ch<>  do          begin            read(ch);            temp:=temp+ch;          end;      delete(temp,length(temp),1);      if temp=End then exit;      readln(a,b);      case temp of         Add:update(a,b,1,n,1);         Query:writeln(query(a,b,1,n,1));         Sub:update(a,-b,1,n,1);      end;    end;end;procedure main;var i,t,n:longint;begin  readln(t);  for i:=1 to t do     begin        readln(n);        build(1,n,1);        readln;        ques(n);     end;end;begin  main;end.

   但是,我们如果对于区间有修改的话,这样就太慢了,O(Qnlogn),甚至比朴素算法都慢

   那么,线段树的精华出现了,lazy-tag技术

    Lazy-Tag 顾名思义,懒惰标记。我们每当要对一个区间进行修改时,

    我们只需要访问到这个区间所包含的最大区间,然后对这个区间记一个lazy-tag

    我们如此做的动机是:没有必要更新到叶子节点,而是在一个合适的范围内,上一个tag

    而我们在询问的时候,每询问一个区间,查询其tag,若存在tag,则把tag下传到该区间的左儿子与右儿子,并把该区间的tag信息上传,且清空当前Tag。

    这样我们能大大的增加效率。

    pushdown应该如何写呢?

      大概的结构是这样

        if lazy[now]<>0 then 

          begin

            do something;

          end;

    我们给出区间修改的问题3

      维护一个数列,支持如下操作:

        1.把区间[l,r]全部增加v

        2.修改k点值为r

        3.询问区间[l,r]的和

    代码如下:(未写main函数)

//区间增减 区间求和const maxn=600001;var lazy,tree:array [0..maxn] of longint;procedure pushup(now:longint);var left,right:longint;begin    left:=now<<1; right:=left+1;    tree[now]:=tree[left]+tree[right];end;procedure pushdown(now,l,r:longint);var len,left,right,delta:longint;begin    left:=now<<1;  right:=left+1;  delta:=lazy[now]; len:=r-l+1;    if lazy[now]<>0 then        begin            inc(tree[now],delta*len);            inc(lazy[left],delta);            inc(lazy[right],delta);            lazy[now]:=0;        end;end;procedure build(l,r,now:longint);var mid,left,right:longint;begin    mid:=(l+r)>>1; left:=now<<1; right:=now+1;    lazy[now]:=0;    if l=r then        begin            read(tree[now]);            exit;        end;    build(l,mid,left);    build(mid+1,r,right);    pushup(now);end;procedure update(now,l,r:longint);var mid,left,right:longint;begin    mid:=(l+r)>>1; left:=now<<1; right:=left+1;    pushdown(left,l,mid);    pushdown(right,mid+1,r);    pushup(now);end;procedure insert(left,right,c,l,r,now:longint);var mid,leftch,rightch:longint;begin    mid:=(l+r)>>1; leftch:=now<<1; rightch:=leftch+1;    pushdown(now,l,r);    if (left<=l) and (r<=right) then        begin            inc(lazy[now],c);            exit;        end;    if left<=mid then insert(left,right,c,l,mid,leftch);    if mid>right then insert(left,right,c,mid+1,r,rightch);    update(now,l,r);end;function querysum(left,right,l,r,now:longint):longint;var leftch,rightch,mid,ans:longint;begin    pushdown(now,l,r);    if (left<=l) and (r<=right) then exit(tree[now]);    mid:=(l+r) shr 1;    leftch:=now<<1;    rightch:=leftch+1;    ans:=0;    if left<=mid then inc(ans,querysum(left,right,l,mid,leftch));    if right>mid then inc(ans,querysum(left,right,mid+1,r,rightch));    exit(ans);end;

   我们再升级一下问题

      维护一个数列,支持如下操作:

        0.询问区间[l,r]的和

        1.修改单点l值为r

        2.把区间[l,r]全部置为v

        3.把区间[l,r]全部增加v

  看上去很麻烦,我们不知道区间覆盖和区间增减的顺序的话,可能标记会出错。

  但是我们只需要再维护一个sign域即可,而我们也不必在意区间覆盖和区间增减的顺序

  因为:当区间覆盖与区间增量tag同时存在时,我们优先区间覆盖标记,在清空区间覆盖标记时,把区间增量标记清空

    为什么呢?很显然,我们先进行区间增减,再进行区间覆盖,那么显然区间增减无意义。

    但是问题来了,若我们先进行的区间覆盖,再进行区间增减,那么区间增减也会被覆盖掉,这样显然会WA.

    怎么解决呢?我们在下tag时,都查询一次当前结点的tag,若当前结点存在tag,那么我们清空tag,使该层tag传递到下一层,

    即当前更新不影响历史记录。

    这样,我们能保持标记总是sign在上,不影响delta的传递,即覆盖标记永远优先于增量标记,且传递深度总是较增量标记传递深度大一层。

    代码如下:(不支持全部覆盖为0,若要全部覆盖为0则需重新初始化sign的值)

    
const maxn=800001;var tree,sign,delta:array [0..maxn] of longint;procedure pushup(now:longint);var left,right:longint;begin    left:=now<<1; right:=left+1;    tree[now]:=tree[left]+tree[right];end;procedure pushdown(now,l,r:longint);var left,right,len:longint;begin    left:=now<<1; right:=left+1;    len:=r-l+1;    if sign[now]<>0 then        begin            sign[left]:=sign[now];            sign[right]:=sign[now];            delta[left]:=0;            delta[right]:=0;            tree[now]:=len*sign[now];            sign[now]:=0;        end;    if delta[now]<>0 then        begin            inc(delta[left],delta[now]);            inc(delta[right],delta[now]);            inc(tree[now],delta[now]*len);            delta[now]:=0;        end;end;procedure update(now,l,r:longint);var mid,left,right:longint;begin    mid:=(l+r)>>1; left:=now<<1; right:=left+1;    pushdown(left,l,mid);    pushdown(right,mid+1,r);    pushup(now);end;procedure build(now,l,r:longint);var mid,left,right:longint;begin    mid:=(l+r)>>1; left:=now<<1; right:=left+1;    delta[now]:=0; sign[now]:=0;    if l=r then        begin            read(tree[now]);            exit;        end;    build(left,l,mid);    build(right,mid+1,r);    pushup(now);end;procedure changepoint(pos,v,l,r,now:longint);var mid,left,right:longint;begin    mid:=(l+r)>>1; left:=now<<1; right:=left+1;    pushdown(now,l,r);    if l=r then        begin            tree[now]:=v;            exit;        end;    if pos<=mid then changepoint(pos,v,l,mid,left)    else changepoint(pos,v,mid+1,r,right);    update(now,l,r);end;procedure change(left,right,v,l,r,now:longint);var mid,leftch,rightch:longint;begin    mid:=(l+r)>>1; leftch:=now<<1; rightch:=leftch+1;    if (l<=left) and (r<=right) then        begin            sign[now]:=v;            delta[now]:=0;            exit;        end;    if mid>=right then change(left,right,v,l,mid,leftch);    if left>mid then change(left,right,v,mid+1,r,rightch);    update(now,l,r);end;procedure insert(left,right,v,l,r,now:longint);var mid,leftch,rightch:longint;begin    mid:=(l+r)>>1; leftch:=now<<1; rightch:=leftch+1;    pushdown(now,l,r);    if (left<=l) and (r<=right) then        begin            inc(delta[now],v);            exit;        end;    if mid>=right then insert(left,right,v,l,mid,leftch);    if left>mid then insert(left,right,v,mid+1,r,rightch);    update(now,l,r);end;function querysum(left,right,l,r,now:longint):longint;var leftch,rightch,mid:longint;begin    pushdown(now,l,r);    if (left<=l) and (r<=right) then exit(tree[now]);    mid:=(l+r)>>10;    leftch:=now<<1;    rightch:=leftch+1;    if left<=mid then exit(querysum(left,right,l,mid,leftch));    if right>mid then exit(querysum(left,right,mid+1,r,rightch));end;procedure main;var i,n,m,que,l,r,a:longint;begin    read(n,m);    build(1,1,n);    for i:=1 to m do        begin            read(que,l,r);            case que of                0:writeln(querysum(l,r,1,n,1));                1:changepoint(l,r,1,n,1);                2:                    begin                        read(a);                        change(l,r,a,1,n,1);                    end;                3:                    begin                        read(a);                        insert(l,r,a,1,n,1);                    end;                end;        end;    end;begin    main;end.
View Code

    另外:

    线段树一定要用数组,指针常数巨大。

    下面是指针与数组版本的耗时比较

     

         此为指针版,耗时耗空间都相当大(不排除本人蒟蒻原因写丑了)

     

        此为数组版,常数还是比较小的。

 

Pascal 线段树 lazy-tag 模板