分享｜关于线段树lazy的那些事
Athanasy
757
2023.08.19
2023.08.28
发布于 未知归属地
线段树Python技术交流

发现好像原题解处扣友还需搜,就单独出一篇文章了

原地址关于线段树lazy的那些事

对于线段树来说,实现方式主要有 预先分配大小/动态开点 这两种分配方案.预先分配大小就是常说的4*n空间大小,动态开点则是当节点为空,并且需要的时候在开辟空间.后者常数大一些,但灵活性和可debug性尽享十足.这里以动态开点进行讲解lazy是什么?

先来思考下一个线段树的节点应该存有哪些信息:

Python
class Node:
    __slots__ = "l", "mid", "r", "lazy", "val", "left", "right"

    def __init__(self, l: int, r: int, val: int = 0, left: 'Node' = None, right: 'Node' = None):
        self.l = l
        self.r = r
        self.mid = (l + r) >> 1
        self.val = val
        self.left = left
        self.right = right
        self.lazy = False

以上述最基本的Node为例.l,mid,r表示为[l,r]区间,及其中点mid,这里我们通常的可以考虑增加一个额外的元素len=r-l+1,记录区间长度,在涉及到区间修改的增加与删除的时候常常会用到这个元素,left和right则又是一组Node,代表着左右节点.

Val

为啥要把线段树的value单独拿出来说呢,那是因为这个value不仅可以表示为值之类的东西,还可以表示为"区间状态".比如摩尔投票法中的两个竞争量状态的合并,dp当中的几个量的合并等等.

PushUp

作为线段树最重要的函数之一:PushUp
它的功能很简单:合并左右节点信息,更新父亲节点信息.
常见的有

  • val记录区间和,那么node.val=node.left.val+node.right.val
  • val记录区间最值,那么node.val=max(node.left.val,node.right.val)
  • val记录一些状态量,假如Merge(x,y)表示合并规则

    node.val=Merge(node.left.val,node,right.val)

PushDown

pushDown操作对于线段树来说有着意义非凡的意义.常常有两个功能:

  1. 动态开点,开辟空间
  2. 更新lazy
Python
def push_down(node: 'Node'):
    if node.left is None:
        node.left = Node(node.l, node.mid)
    if node.right is None:
        node.right = Node(node.mid + 1, node.r)
    # if node.lazy:
    #     xxxxxxxx

Lazy

lazy是什么,lazy其实又称之为懒标记.通常应用于"区间修改"类问题.对于区间修改,我们先来看看单点修改函数:

Python
def update(x:int,val:int,node:'Node'):
    if node.l==node.r:
        node.val=val
        return
    pushDown(node)
    if x<=node.mid:
        update(x,val,node.left)
    else:
        update(x,val,node.right)
    pushUp(node)

那么我们来照着模仿写一个区间修改函数(这里以区间最值为例):

Python
def update(l:int,r:int,val:int,node:'Node'):
    if l<=node.l and node.r<=r:
        node.val=val
        #node.lazy=val
        return
    pushDown(node)
    if l<=node.mid:
        update(l,r,val,node.left)
    if r>node.mid:
        update(l,r,val,node.right)
    pushUp(node)

有问题吗?显然是有的,当我们更新到node处于[l,r]的区间的时候就停止了更新,那么子区间是没有更新到的,但如果暴力更新呢?

Python
def update(l:int,r:int,val:int,node:'Node'):
    if node.l==node.r:
        node.val=val
        #node.lazy=val
        return
    pushDown(node)
    if l<=node.mid:
        update(l,r,val,node.left)
    if r>node.mid:
        update(l,r,val,node.right)
    pushUp(node)

直接更新整个区间[l,r],树上不直观是吧。那么我们想想一段序列,更新[l,r],你暴力更新和查询的复杂度是多少?(如果是足矣接受的,我们还需要差分这类工具干嘛)
所以第二种暴力更新的解法复杂度显然高达o(n),而第一种则是o(logn),但第一种我们却没更新到子区间,怎么办?后面还要查子区间的信息.

延迟更新

延迟更新其实就是给需要更新的区间打上lazy标记,我们当需要查/改到这些区间的时候去改.以这题翻转为例:

0 0 0 0 0这是一段序列[1,5]范围

考虑有几个Node(自上向下,从左往右):[1,5]、[1,3]、[4,5]、[1,2]、[3,3]、[4,4]、[5,5]、[1,1]、[2,2]

翻转[1,5]

1 1 1 1 1这是翻转后的区间,而这个翻转后的情况:保留在[1,5],而它下面的两个子节点区间[1,3]、[4,5]则不更新,而是打上lazy标记True,表示我接下来如果要查这个区间或者修改这个区间,那么是需要翻转的.当然连续打上两次的lazy区间,相当于翻转两次,等于不变,所以我们可以在psuhDown去写当查到lazy的区间以后:它的子区间也要相应的去更新lazy=>这就是所谓的lazy下传.(思考下pushDown下传几层)实际每次下传一层就行,你查询的不一定是一个点[x,x]这样的区间,比如以上述为例,查询[1,3],那么你的lazy只需要更新到[1,3]就行,不需要继续向下更新
范例代码:

Python
def push_down(node: 'Node'):
    if node.left is None:
        node.left = Node(node.l, node.mid)
    if node.right is None:
        node.right = Node(node.mid + 1, node.r)
    # 需要翻转
    if node.lazy:
        # 用0/1表示是否翻转
        # 区间进行翻转,伪代码函数Revers,这里很灵活,考虑翻转后的区间信息变化和更新,例如区间1的个数=区间长度-区间原个数
        Revers(node.left)
        Revers(node.right)
        # 可以看出多次翻转可能最后不需要翻转的
        node.left.lazy ^= 1
        node.right.lazy ^= 1
        node.lazy = 0

那么记得在update和query的时候进行pushDown的操作来判断是否需要在更新/查询之前去更新区间的状态:
是的,lazy也可以看作当前区间的一个状态,是否需要被更新的状态
Lazy是十分灵活的,读者应至少掌握常见的区间修改,区间求和/区间翻转,区间求和/区间覆盖,区间最值这三类常见lazy的使用,才能有更好的lazy理解

  1. 区间翻转/区间求和
    此处lazy表示区间是否翻转状态
Python
def push_down(node: 'Node'):
    if node.left is None:
        node.left = Node(node.l, node.mid)
    if node.right is None:
        node.right = Node(node.mid + 1, node.r)
    # 需要翻转
    if node.lazy:
        # 用0/1表示是否翻转
        # 区间进行翻转,这里很灵活,考虑翻转后的区间信息变化和更新,例如区间1的个数=区间长度-区间原个数
        node.left.val = node.left.length - node.left.val
        node.right.val = node.right.length - node.right.val
        # 可以看出多次翻转可能最后不需要翻转的
        node.left.lazy ^= 1
        node.right.lazy ^= 1
        node.lazy = 0
  1. 区间整体加上一个数/区间求和:
    这里lazy表示的是"需要加上的数",用这个需要加上的数去更新区间和
Python
def push_down(node: 'Node'):
    if node.left is None:
        node.left = Node(node.l, node.mid)
    if node.right is None:
        node.right = Node(node.mid + 1, node.r)
    # 需要加上不为0的数
    if node.lazy:
        # 区间每个数都加了这个数,值增加区间长度*这个数
        node.left.val += node.left.len * node.lazy
        node.right.val += node.right.len * node.lazy
        # 原来可能也有需要累加的数,合并lazy
        node.left.lazy += node.lazy
        node.right.lazy += node.lazy
        node.lazy = 0
  1. 区间覆盖/区间最值更新
    这里用一个数覆盖区间,并更新区间最值,lazy显然为需要覆盖区间的数,覆盖了最值显然就是这个数
Python
def push_down(node: 'Node'):
    if node.left is None:
        node.left = Node(node.l, node.mid)
    if node.right is None:
        node.right = Node(node.mid + 1, node.r)
    # 覆盖的数是存在于题目范围里的例如[-1e7,1e7],inf表示不在这个范围的数的状态,即此时不需要覆盖
    # 为什么不用0,因为可能会用0覆盖区间
    if node.lazy != inf:
        # 最值覆盖
        node.left.val = node.lazy
        node.right.val = node.lazy
        # 后面用来覆盖的数,实际上应该覆盖前面覆盖的数
        node.left.lazy = node.lazy
        node.right.lazy = node.lazy
        node.lazy = inf

这三个常见lazy是读者需要掌握的,这样遇到新的lazy类型的题,读者将会有更深层的更新思考,pushDown的正确书写.

PushDown时机

那么什么时候需要psuhDonw,在update和query时,我们知道都有个return函数,假如当前node还没有达到return的要求,那么显而易见的是,答案在他的子树上,我们应该及时的pushDown更新下一层子树信息才能保证下一次查找的数据的正确性
范例:

Python
Python
def update(l:int,r:int,x:int,node:'Node'):
    if l<=node.l and node.r<=r:
        node.val=x
        node.lazy^=1
        return
    #在下次更新前及时更新
    pushDown(node)
    if l<=node.mid:
        update(l,r,node.left)
    if r>node.mid:
        update(l,r,node.right)
    pushUp(node)

线段树最后的细节:

咱一直在说Node,Node,那线段树人家是树啊,有Root啊,所以我个人喜欢这样的一个写法:

Python
class Node:
    xxxxx


def pushDown(node: 'Node'):
    xxxx


def pushUp(node: 'Node'):
    xxxx


class Seg:
    def __init__(self):
        # 动态开点,在没有build的情况下,想开多大就开多大,表示的是最终区间范围[l,r]
        self.root = Node(l, r)
    def update(self,l:int,r:int,val:int,node:'Node'=None):
        if node is None:
            node=self.root
        xxxxx
    def query(self,l:int,r:int,node:'Node'=None):
        if node is None:
            node=self.root
        xxxx

__slots__ ="l","mid","r","left","right","val","lazy"
这是py线段树的一个小技巧,使用self临时赋值线段树的Node属性,会比较慢,使用上述可以为每个Node直接开好属性,速度快上不少,但无法再用self添加新值,都线段树了,还会添加啥新字段

题目原地址:更新数组后处理求和查询

本题代码参考

Python
class Node:
    __slots__ = "l", "r", "mid", "leng", "val", "lazy", "left", "right"

    def __init__(self, l, r):
        self.l = l
        self.r = r
        self.mid = (l + r) >> 1
        self.leng = r - l + 1
        # 是否翻转,0是不翻转,1是翻转
        self.lazy = 0
        self.left = None
        self.right = None
        self.val = 0


def push_up(node):
    node.val = node.left.val + node.right.val


def push_down(node):
    if node.left is None:
        node.left = Node(node.l, node.mid)
    if node.right is None:
        node.right = Node(node.mid + 1, node.r)
    if node.lazy:
        node.lazy = 0
        node.left.lazy ^= 1
        node.right.lazy ^= 1
        node.left.val = node.left.leng - node.left.val
        node.right.val = node.right.leng - node.right.val


class Solution:
    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:
        n = len(nums1)
        root = Node(0, n - 1)

        def build(node):
            if node.l == node.r:
                node.val = nums1[node.l]
                return
            push_down(node)
            build(node.left)
            build(node.right)
            push_up(node)

        build(root)
        ans = []
        s = sum(nums2)
        self.root = root
        for u, l, r in queries:
            if u == 1:
                self.update(l, r)
            elif u == 2:
                s += self.root.val * l
            else:
                ans.append(s)
        return ans

    def update(self, l: int, r: int, node: 'Node' = None):
        if node is None:
            node = self.root
        if l <= node.l and node.r <= r:
            node.val = node.leng - node.val
            node.lazy ^= 1
            return
        # 本处是为了推送lazy,而不再是为了开点了(build时候满二叉树),其实此处已经蕴含了查询功能了,push_down到更改的最小区间,push_up到上方影响区间
        push_down(node)
        if l <= node.mid:
            self.update(l, r, node.left)
        if r > node.mid:
            self.update(l, r, node.right)
        push_up(node)

最后

动态开点线段树有个常见的应用就是权值线段树,想要学习主席树和权值线段树和平衡树的扣友可以参照我以下文章:

静态主席树教程

平衡树总结(上)

平衡树总结(下)

评论 (0)