如何做攻击类型网站,最新网页游戏排行榜2021,用户权限网站,甘肃网站建设公司文章目录前言特点操作数据存储updateLazy下移查询实现前言
月末了#xff0c;划个水#xff0c;赶一下指标#xff08;更新一些活跃值#xff0c;狗头#xff09; 本文主要是关于线段树的内容。这个线段树的话#xff0c;主要是适合求解我们一个数组的一些区间的问题划个水赶一下指标更新一些活跃值狗头 本文主要是关于线段树的内容。这个线段树的话主要是适合求解我们一个数组的一些区间的问题例如区间之和区间乘机区间最大最小值等当然求和求乘机啥的直接用前缀数组如果是一些区间的大小的问题的话当然用这个是比较合适的当然这依然是空间换取时间的操作。例如一个数组长度为N那么当我们构建这颗线段树时我们所需要花费的空间为4N为了保证不越界).
特点
首先的话要说的关于线段树的特点其实就几个第一就是数据存放在叶子节点非叶子节点表示的是我们想要求取的目标值例如我们想要求取一个区间和那么非叶子节点存储的就是这个小区间内的值。
第二个特点就是Lazy懒惰更新这个有点类似于摊还分析当中提到的第二种方式每个元素的花费需要考虑到当前的消费和将来的消费将来的消费用于将来的花费。这个Lazy其实也有类似的意思我先标记一下然后我要用的到的时候我再进行操作起到了一个预知未来延迟操作的意思。同样的代码实现比较简单至少比红黑树斐波那契堆简单。
那么关于这个特点的话这里先插一个眼具体的将在下面进行阐述。 本文的话就从区间求和为案例进行说明这里面可以覆盖到较多的操作。
操作
数据存储
首先的话这个数据的存储其实就是下面的样子。 然后这个叶子节点的话就是我们的这个数据然后的话这里也是对半砍掉一组数据然后递归跟那个归并有点像。
update
然后就是修改这个的话就开始体现到Lazy的作用了首先我们知道一个节点他其实表示了当前这个节点表示的是哪个区间的一个值用代码表示他的一个数据结构其实就是这样的
class __Node():l: int 0r: int 0v: int 0lazy: int 0def __str__(self):return left:{},right{},value:{},lazy:{}.format(self.l, self.r, self.v, self.lazy)
所以这个Update的话明确一个区间然后呢我们找到这个区间然后秉承着lazy的原则如果我们发现如果我们要更新的区间能够覆盖我们当前的这个节点的区间我们就直接更新好这个节点的值然后这个Lazy记录一些我们修改的值是啥。 def update(self, i, l, r, k):if (self.tree[i].l l and self.tree[i].r r):self.tree[i].v k * (self.tree[i].r - self.tree[i].l 1)self.tree[i].lazy kreturnif (self.tree[i].lazy ! 0):self.__putdown(i)if (self.tree[2 * i].r l): #和左孩子还有交集self.update(2 * i, l, r, k)if (self.tree[2 * i 1].l r): #和右孩子还有交集self.update(2 * i 1, l, r, k)self.tree[i].v self.tree[2*i].vself.tree[2*i1].v之后的话我们跟新一下当然这里还需要注意的是就是如果没有完全覆盖的话我们需要更新一下Lazy此时给到孩子节点为什么要更新呢原因的话就是当前的节点已经不能覆盖了需要用到孩子节点但是原来孩子节点没有更新值现在要用了就得把孩子赶紧更新一下然后重新更新当前作为父节点的i。
Lazy下移
这个下移的话就是刚刚提到的因为这个Lazy就相当于一个标记。他是这样的。 def __putdown(self, i):self.tree[2 * i].lazy self.tree[i].lazyself.tree[2 * i 1].lazy self.tree[i].lazymid (self.tree[i].l self.tree[i].r) // 2self.tree[2 * i].v self.tree[i].lazy * (mid - self.tree[i].l 1)self.tree[2 * i 1].v self.tree[i].lazy * (self.tree[i].r - mid)self.tree[i].lazy 0
更新孩子的Lazy然后去掉父节点的Lazy然后更新值。
查询
查询也是一致的和更新一样只是少了元素的更新这里依然需要这个Lazy的下移而且其实这个Lazy的下移其实就是在重新计算我们的修改假设一直都没有用到就一直不会更新这样就节省了运算。就比如你买了一张4080ti,但是你一直没有时间happy那么在你没有happy时间的情况下就提前买了显卡那么就浪费了这个money因为早买没有享受到但是当你有happy time的时候你再去买那么就是及时享乐了没有造成资源的空闲浪费搞不好还降价了嘿嘿~
def search(self, i, l, r):if (self.tree[i].l l and self.tree[i].r r):return self.tree[i].vif (self.tree[i].lazy ! 0):self.__putdown(i)t 0if (self.tree[2 * i].r l):t self.search(2 * i, l, r)if (self.tree[2 * i 1].l r):t self.search(2 * i 1, l, r)return t实现 为了方便建树这里的话我们将从1开始作为我们的下标class SegmentTree(object):def __init__(self, date):self.date [0] dateself.len_date len(self.date)self.tree [self.__Node() for _ in range(4 * self.len_date)]self.__build(1, 1, self.len_date - 1)def __build(self, i, l, r):self.tree[i].l lself.tree[i].r rif (l r):self.tree[i].v self.date[r]returnmid (l r) // 2self.__build(2*i, l, mid)self.__build(2*i1, mid 1, r)self.tree[i].v self.tree[i * 2].v self.tree[i * 2 1].vdef search(self, i, l, r):if (self.tree[i].l l and self.tree[i].r r):return self.tree[i].vif (self.tree[i].lazy ! 0):self.__putdown(i)t 0if (self.tree[2 * i].r l):t self.search(2 * i, l, r)if (self.tree[2 * i 1].l r):t self.search(2 * i 1, l, r)return tdef update(self, i, l, r, k):if (self.tree[i].l l and self.tree[i].r r):self.tree[i].v k * (self.tree[i].r - self.tree[i].l 1)self.tree[i].lazy kreturnif (self.tree[i].lazy ! 0):self.__putdown(i)if (self.tree[2 * i].r l):self.update(2 * i, l, r, k)if (self.tree[2 * i 1].l r):self.update(2 * i 1, l, r, k)self.tree[i].v self.tree[2*i].vself.tree[2*i1].vdef __putdown(self, i):self.tree[2 * i].lazy self.tree[i].lazyself.tree[2 * i 1].lazy self.tree[i].lazymid (self.tree[i].l self.tree[i].r) // 2self.tree[2 * i].v self.tree[i].lazy * (mid - self.tree[i].l 1)self.tree[2 * i 1].v self.tree[i].lazy * (self.tree[i].r - mid)self.tree[i].lazy 0class __Node():l: int 0r: int 0v: int 0lazy: int 0def __str__(self):return left:{},right{},value:{},lazy:{}.format(self.l, self.r, self.v, self.lazy)
这里的话注意找的时候呢是从1号节点开始的1号节点不等于第一个元素
if __name__ __main__:a [1,2,3,4,5]seg SegmentTree(a)seg.update(1,5,5,5) #从根节点开始找更新区间为[5,5]的元素5也就是第五个元素5print(seg.search(1, 4, 5))#从根节点开始找查找区间为[4,5]的区间和over
