关于使用lazytag的线段树两种查询方式的比较研究

说到线段树,想来大家并不陌生——最基本的思路就是将其规划成块,然后只要每次修改时维护一下即可。

但是尤其是涉及到区间修改时,lazytag的使用往往能够对于程序的质量起到决定性作用(Ex:一般JSOI2008左右的线段树题目,如果有区间修改的话,那么假如普普通通的一个个修改的话,那么一般30分左右,甚至更少;而有了神奇的lazytag,只要别的地方写的还算基本到位,一般就Accept了)

lazytag的基本思想也就是在需要修改的区间打上标记,然后下次动态维护标记和真正值之间的关系,然后查询或者下一个修改操作涉及此区间时,进行进一步维护。

于是,此时就存在两种不同的查询操作了(此处以BZOJ1798为例)

方案一:当查询过程中,遇到了带有标记的点,则将其记录下来(即并入综合的修改参数里面),然后当刚好找到合适区间是,再操作之

1 function cal(z,x,y,l,r:longint;d:vet):int64;inline;
2          var d1:vet;
3          begin
4               if l>r then exit(0);
5               d1:=merge(b[z],d);
6               if (x=l) and (y=r) then exit(((a[z]*d1.a0) mod p+(d1.a1*((r-l+1) mod p)) mod p) mod p);
7               exit((cal(z*2,x,(x+y) div 2,l,min((x+y) div 2,r),d1)+cal(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r,d1)) mod p);
8          end;

这个方案在操作时,实际上并没有动任何的标记,直接通过现有的标记求出了值

方案二:查询过程中遇到标记点的话,则将其扩展下去,保证一路下来都不存在标记点,然后到地方了之后直接返回数值

1 function cal(z,x,y,l,r:longint):int64;inline;
2          begin
3               if l>r then exit(0);
4               ext(z,x,y);
5               if (x=l) and (y=r) then exit(a[z]);
6               exit((cal(z*2,x,(x+y) div 2,l,min((x+y) div 2,r))+cal(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r)) mod p);
7          end;

附:ext操作和merge操作

 1 function merge(d1,d2:vet):vet;inline;
 2          var d3:vet;
 3          begin
 4               d3:=d1;
 5               d3.a0:=d3.a0 mod p;d3.a1:=d3.a1 mod p;
 6               d2.a0:=d2.a0 mod p;d2.a1:=d2.a1 mod p;
 7               d3.a0:=(d3.a0*d2.a0) mod p;
 8               d3.a1:=((d3.a1*d2.a0) mod p+d2.a1) mod p;
 9               exit(d3);
10          end;
11 procedure ext(z,x,y:longint);inline;
12           begin
13                a[z]:=((a[z]*b[z].a0) mod p+(b[z].a1*((y-x+1) mod p)) mod p) mod p;
14                b[z*2]:=merge(b[z*2],b[z]);
15                b[z*2+1]:=merge(b[z*2+1],b[z]);
16                b[z].a0:=1;b[z].a1:=0;
17           end;

此方法比较直观,比较好想,但是看样子好多标记其实被操作了

好了,现在看下时间对比:(注:此两个程序中除了cal函数不一样其他均一样)

方案一:

方案二:(这个里面方案一的cal函数是通过{}注释掉的,所以代码会多出来那么些)

空间上差不多(phile:这不显然的么呵呵呵),时间上方案一要快,原因其实还是因为方案一并没有涉及到修改标记的操作,而方案二涉及了,而且尤其对于tag很密集的树,操作更是会较为复杂。还有方案二虽然更加直观易想,但是代码其实并没有缩减,两者代码复杂度几乎一样。所以综合而言,方案一更加划算么么哒

下面附上BZOJ1798代码

  1 /**************************************************************
  2     Problem: 1798
  3     User: HansBug
  4     Language: Pascal
  5     Result: Accepted
  6     Time:22432 ms
  7     Memory:31492 kb
  8 ****************************************************************/
  9  
 10 type
 11     vet=record
 12               a0,a1:int64;
 13     end;
 14 var
 15    i,j,k,l,m,n,a2,a3,a4:longint;
 16    p:int64;
 17    a,c:array[0..1000000] of int64;
 18    b:array[0..1000000] of vet;
 19    d,d1:vet;
 20 procedure built(z,x,y:longint);inline;
 21           begin
 22                if x=y then
 23                   a[z]:=c[x] mod p
 24                else
 25                    begin
 26                         built(z*2,x,(x+y) div 2);
 27                         built(z*2+1,(x+y) div 2+1,y);
 28                         a[z]:=(a[z*2]+a[z*2+1]) mod p;
 29                    end;
 30                b[z].a0:=1;b[z].a1:=0;
 31           end;
 32 function max(x,y:longint):longint;inline;
 33          begin
 34               if x>y then max:=x else max:=y;
 35          end;
 36 function min(x,y:longint):longint;inline;
 37          begin
 38               if x<y then min:=x else min:=y;
 39          end;
 40 function merge(d1,d2:vet):vet;inline;
 41          var d3:vet;
 42          begin
 43               d3:=d1;
 44               d3.a0:=d3.a0 mod p;d3.a1:=d3.a1 mod p;
 45               d2.a0:=d2.a0 mod p;d2.a1:=d2.a1 mod p;
 46               d3.a0:=(d3.a0*d2.a0) mod p;
 47               d3.a1:=((d3.a1*d2.a0) mod p+d2.a1) mod p;
 48               exit(d3);
 49          end;
 50 procedure ext(z,x,y:longint);inline;
 51           begin
 52                a[z]:=((a[z]*b[z].a0) mod p+(b[z].a1*((y-x+1) mod p)) mod p) mod p;
 53                b[z*2]:=merge(b[z*2],b[z]);
 54                b[z*2+1]:=merge(b[z*2+1],b[z]);
 55                b[z].a0:=1;b[z].a1:=0;
 56           end;
 57 function op(z,x,y,l,r:longint;d:vet):int64;inline;
 58          var
 59             a3,a4:int64;
 60          begin
 61               if l>r then exit(0);
 62               ext(z,x,y);
 63               if (x=l) and (y=r) then
 64                  begin
 65                       b[z]:=d;
 66                       exit(((a[z]*((b[z].a0-1) mod p)) mod p+(b[z].a1*((r-l+1) mod p)) mod p) mod p);
 67                  end
 68               else
 69                   begin
 70                        a3:=op(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2),d);
 71                        a4:=op(z*2+1,(x+y) div 2+1,y,max(l,(x+y) div 2+1),r,d);
 72                        a[z]:=(a[z]+(a3+a4) mod p) mod p;
 73                        exit((a3+a4) mod p);
 74                   end;
 75          end;
 76 {function cal(z,x,y,l,r:longint;d:vet):int64;inline;  //方案一
 77          var d1:vet;
 78          begin
 79               if l>r then exit(0);
 80               d1:=merge(b[z],d);
 81               if (x=l) and (y=r) then exit(((a[z]*d1.a0) mod p+(d1.a1*((r-l+1) mod p)) mod p) mod p);
 82               exit((cal(z*2,x,(x+y) div 2,l,min((x+y) div 2,r),d1)+cal(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r,d1)) mod p);
 83          end;     }
 84 function cal(z,x,y,l,r:longint):int64;inline;  //方案二
 85          begin
 86               if l>r then exit(0);
 87               ext(z,x,y);
 88               if (x=l) and (y=r) then exit(a[z]);
 89               exit((cal(z*2,x,(x+y) div 2,l,min((x+y) div 2,r))+cal(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r)) mod p);
 90          end;
 91  
 92 function modd(x:int64):int64;inline;
 93          begin
 94               if x>=0 then exit(x mod p);
 95               modd:=((abs(x) div p+1)*p+x) mod p;
 96          end;
 97  
 98 begin
 99      readln(n,p);
100      for i:=1 to n do read(c[i]);
101      readln;
102      built(1,1,n);
103      readln(m);
104      for i:=1 to m do
105          begin
106               read(j);
107               case j of
108                    1:begin
109                           readln(a2,a3,a4);
110                           d.a0:=a4;d.a1:=0;
111                           op(1,1,n,a2,a3,d);
112                    end;
113                    2:begin
114                           readln(a2,a3,a4);
115                           d.a0:=1;d.a1:=a4;
116                           op(1,1,n,a2,a3,d);
117                    end;
118                    3:begin
119                           readln(a2,a3);
120                           writeln(modd(cal(1,1,n,a2,a3)));
121                    end;
122               end;
123          end;
124 end.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏mukekeheart的iOS之旅

MySQL学习笔记(一)

一、MySQL基础知识 MySQL 是一个真正的多用户、多线程 SQL 数据库服务器。 SQL(结构化查询语言)是世界上最流行的和标准化的数据库语言。MySQL...

2438
来自专栏人人都是极客

环形缓冲区的实现

队列 (Queue):是一种先进先出(First In First Out ,简称 FIFO)的线性表,只允许在一端插入(入队),在另一端进行删除(出队)。

2173
来自专栏决胜机器学习

有趣的算法(四)——一致性Hash算法模拟redis集群

有趣的算法(四)——一致性Hash算法模拟redis集群 (原创内容,转载请注明来源,谢谢) 一、概述 redis的集群,对key存储在哪个服务器的问题上,采...

3277
来自专栏小鹏的专栏

windows下C++如何调用matlab程序

实验平台:    matlab R2016b   VS2013 思路: 1. 设置matlab的编译器,使用外部的VC或者gcc等编译器。 2. 编译m文件成d...

2249
来自专栏同步博客

memcached分布式缓存

  memcached虽然称为“分布式”缓存服务器,但服务器端并没有“分布式”功能。Memcache集群主机不能够相互通信传输数据,它的“分布式”是基于客户端的...

1111
来自专栏用户画像

Python 使用正则表达式进行MongoDB条件查询

db.VideoProfile.find( {_id: { $regex: /^1_[0-9]{5,}$/} } ).count()

902
来自专栏游戏杂谈

Unity中巧用协程和游戏对象的生命周期处理游戏重启的问题

主要用到协程(Coroutines)和游戏对象的生命周期(GameObject Lifecycle)基础知识,巧妙解决了游戏重启的问题。

3252
来自专栏XAI

【定制化图像开放平台】入门实例之手写数字模型训练

本帖主要用手写数字为例进行一个简单入门实例总结(非官方) 平台网站:http://ai.baidu.com/customize/app/model/ 定制化图像...

41416
来自专栏Golang语言社区

数据说话:Go语言的Switch和Map性能实测

在开发pgx(一个针对Go语言的PostgreSQL driver)的时候,有好几次我都需要在20多个代码分支间跳转。通常我会选用switch语句。还有个更加可...

4015
来自专栏深度学习那些事儿

提升python项目完成效率的调试方法技巧(上)

效率提升是极为重要的事情,我们的时间本来就不充裕,不应该过多将时间浪费在调试过程中。对于大型项目光有dubug是不够的,如果需要提高产品调试进度,必须需要采取一...

3767

扫码关注云+社区