首页 > 其他分享 >nove.14 对懒标记的思考

nove.14 对懒标记的思考

时间:2022-11-14 19:23:23浏览次数:64  
标签:下层 nove.14 标记 push 思考 区间 本层 节点

小记
这本来是萌新的时候就该理解的问题,现在来想想清楚
我好笨qwq,但是慢慢想清楚总是好的

今天探究一个问题:线段树对区间值的维护的时刻

一般来说,找到修改区间的时候,在打上懒标记的同时要修改区间值
懒标记只是传给下层节点用的,即懒标记代表了下层节点没有改变的量(而本层节点的值已经改变了)
那么可以不修改本层节点吗?在需要用的时候再修改
对这个问题,写一个最基础的线段树板题就可以验证了

打代码的时候发现了问题,证明了这种方法是不可以的
寻找修改区间的操作:先push_down,再找下层区间,找完后push_up
在push_up的时候,如果下层节点的值没对,那么本层节点的值也是错误的,这导致了算法整体的错误

所以puush_down表示的是本层区间已经改变了、下层区间还没改变的量

标签:下层,nove.14,标记,push,思考,区间,本层,节点
From: https://www.cnblogs.com/antimony-51/p/16890091.html

相关文章

  • 「开源人说」|AI普惠,阿里灵杰开源历程与思考
    简介: 施兴阿里巴巴资深技术专家阿里巴巴开源项目EasyRec负责人以下为开发者社区「开源人说」第四期——大数据&AI专场的主题分享,点击链接了解更多精彩详情......
  • 通过存储过程,插入300万条数据的一点思考?
    1.今天凌晨1点多开始插入数据,到现在为止,一共插入的数据大小,大约是30M数据,但是总量在190M数据左右2.中间我去睡觉,电脑可能也是处于睡眠状态.3.电脑的性能也很大程度决定......
  • 实验一 阅读并思考
    请阅读北航陈彦吉同学的这篇博客中的各参考资料,并回答如下问题:(1)回顾你过去将近3年的学习经历当初你报考的时候,是真正喜欢计算机这个专业吗?答:是的,正是因为感兴趣才......
  • 《结构思考力》
       第一部分结构思考力的核心理念结构化思考力的核心理念是应用结构化思维底层逻辑进行思考、表达和解决问题。高效管理者应当具备三种基本技能:技术性技......
  • 自定义标记
    目录介绍注册标记使用标签介绍自定义标记首先要在pytest.ini文件当中注册也可以通过fixture注册,不注册的话不影响使用但是执行的时候就会有警告注册标记#pytest.in......
  • 标记功能预期失败的用例-xfail
    目录介绍将用例标记失败xfail可用的参数忽略xfail介绍xfail是用来标记那些预期失败的用例,它是一个内部标记将用例标记失败不同的标记方法使用示例@pytest.mark.......
  • 产品小虾米的思考与修正
    1.技术边界在画用户体验地图,or做产品规划的时候,要清楚地明白产品的技术边界是什么。不要以用户的视角仅提出问题,要明白以产品的视角看是否真的可以改进,提升的痛......
  • 简单说 !![]==true 与 []==true 引发的思考
    说明直接说出问题!![]==true//结果是true[]==true//结果是false![]==[]//结果是true为什么会出现这种情况解释首先说一下,如果你看到这些代码,能想到相......
  • C语言实现扫雷(标记/取消标记雷、自动展开)
    前言扫雷的设计和三子棋大同小异。这次我在之前的扫雷基础上加入了标记/取消标记雷和显示雷的数量的功能。希望对大家能有帮助。这里以9*9的棋盘为例。先附上游戏的最终效果......
  • 《失控的正向思考》:真正的正向思考是面对现实的勇气
    《失控的正向思考》作者是美国畅销书作家芭芭拉·艾伦瑞克,她另一本更广为人知的作品是《我在底层的生活:当专栏作家化身女服务生》。《我在底层生活》写作来自这样一个动因:......