源码:

LAZY:区间修改一霸

被Segment区间修改搞晕的蒟蒻们,看向这里······

思路学习致敬:差不多算是转载才怪

没有看过线段树的童鞋:ARFA’s blog

致敬:在上一次线段树的讲解中我没有将l,r记录在数组中,这样无法实现LAZY,请注意。

-

区间修改与LAZY思路

如果你想for i:=l to r do change你就太天真了,区间求和如果像刚才那样,速度几乎跟暴力没有什么区别。像要区间修改,一定要有整体(整棵树)的思想。

LAZY就是“懒”的意思,打出程序后你会觉得它VERY懒,真的。LAZY的主要意思就是,如果你不会查询这一段的和,我就不给你加上add,当你真的要求的时候,我“临时”帮你加上add,然后蒙混过关。但是我的态度不好,你没有查全部的,我就完成你现在查的就行了,剩下的我还是不管。

你会想,哎呦,这不是将改变和查询结为一体(其利断金)吗?我明确的告诉你,YNEOS。

想要实现,必须明白几点。

1
2
3
1.从根往下改变,而不是叶子结点往上递归。
2.lazy是一个单独的数组,他会分配给他的左右儿子。
3.当我查到现在的l,r时候,inc(tree[k],···)

-

LAZY清楚的实例验证

楚的实例验证

看这幅图：

如果1到8全部加1的话,会出现怎样的情况?

我查询1到8的和,tree会增加8(公式是tree[k]+lazy[k]*(right[k]-left[k]+1))你懂的。

由于lazy[1]被查到了,所以分给了lazy[2]和lazy[3]。

第二次我查询2到3,想一想,lazy会被“推”到哪里?

首先推到4和和5对不对?然后在5处消失。(其实5处没有儿子了)然后在4处推往8,因为到9处lazy也不见了。最后lazy的“残骸”就在1,1也就是8。

就是这样的思路一步一步的将“残骸”推下去,是不是很“懒”?当然我称之为“懈怠推”。

-

推理与实现

首先是往下推的程序:
1
2
3
4
5
6
7
8
9
10
11
12
procedure SUC(k:int64);
var
        l,r:int64;
begin
        l:=k*2;                //给左儿子
        r:=k*2+1;            //给右儿子
        inc(lazy[l],lazy[k]);             //继续懒
        inc(lazy[r],lazy[k]);            //继续懒
        inc(tree[l],lazy[k]*(right[l]-left[l]+1));        //实际加成
        inc(tree[r],lazy[k]*(right[r]-left[r]+1));        //实际加成
        lazy[k]:=0;            //清空本次LAZY
end;
然后是区间修改:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
procedure change(k:longint);
    var
            mid:int64;
    begin
            if (left[k]>=x)and(right[k]<=y) then    //如果可以修改
            begin
                    inc(tree[k],add*(right[k]-left[k]+1));//公式
                    inc(lazy[k],add);
                    exit;    //返回
            end;
            if lazy[k]>0 then    //还有LAZY的“残骸”
                    SUC(k);        //往下推
            mid:=(left[k]+right[k]) div 2;    //去儿子那边
            if x<=mid then
                    change(k*2);
            if y>mid then
                    change(k*2+1);
            tree[k]:=tree[k*2]+tree[k*2+1];    //更新
    end;
对于区间求和的影响:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
procedure look(k:longint);
var
        mid:int64;
begin
        if (left[k]>=x)and(right[k]<=y) then
        begin
                inc(find,tree[k]);
                exit;
        end;
        if lazy[k]>0 then
                SUC(k);
        mid:=(left[k]+right[k]) div 2;
        if x<=mid then
                look(k*2);
        if y>mid then
                look(k*2+1);
end;

THANK EvErYBODY!