说到线段树,想来大家并不陌生——最基本的思路就是将其规划成块,然后只要每次修改时维护一下即可。
但是尤其是涉及到区间修改时,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.