关键词：
上篇文章，我们介绍了线段树的基本概念和单点更新、区间查询，今天，我们来接着上次的线段树问题继续深入研究。在解决线段树问题的过程中，我们会遇到要求修改区间中某一元素值的问题，当然也可能会遇到要求修改一段子区间所有值的问题－－即区间更新问题。回忆一下上篇文章单点更新的方法是，由叶节点逐级向上进行更新，此时更新一个节点值的时间复杂度为o（log n），（点击链接了解详情：线段树＋RMQ问题第二弹），那么以这样的处理效率来进行区间更新结果会怎样？现在假设待更新区间数据的规模为 n ，那么就需要进行 n 次单点更新，也就意味着处理的时间复杂度为 o（n＊ log n），这样的时间复杂度其实还是可以接受的，但是，在实际生活中问题怎么可能那么简单就给一个区间呢？这样岂不是让做题的人太舒服了。所以，再假设待查询的区间个数也为 n ，这时候，时间复杂度就变成了 o（n＊n＊log n），如果这个 n 的值再大一点。。。你敢继续往下想吗？
我大概是不敢了，所以现在需要尝试找一种快捷的方法或者在现有的方法基础上进行优化。
通常情况下，如果时间复杂度过高，我们就会考虑牺牲空间来换取时间，利用线段树来解决区间最值查询问题的思路也是如此，那么在区间更新的问题上，我们应该如何合理利用空间换取时间呢？经过分析可以发现，在区间更新的问题中，我们要做的无非就是取一个区间的信息，接着获取更新的方式，最后定位范围进行更新。如果待更新区间中每个元素的更新方式都不同，那没有办法，我们只能因元素而异，对症下药，但如果待更新区间所有元素都遵循统一的更新规则，例如均加上某个常数，那处理起来就会有一致性，我们就可以以此为切入点进行研究。
我们都知道，元素更新问题一般会伴随着查询问题，如果更新与否对当前面对的所有问题不会造成影响，这时候我们可以借鉴赊账的原理，对需要更新但当前不需要查询的区间暂不更新，并把这笔账记下，待需要查询的时候，将这笔账偿清，这样也并不影响查询过程的正确性。有人喜欢赊账，觉得这年头，花呗上没点旧账都不叫生活，但有的人却不喜欢这种透支未来的生活方式。这里我想说在做题的过程中赊点帐还是无伤大雅的，重要的是，这种赊账的思想用在这里还真是恰到好处呢，不信你就往下看。在继续之前，我大胆的猜测一下，会不会有人因为看了我这篇文章，到实践中检验真理，兜里有钱也去花呗上赊点帐玩玩。
现实中我们要赊账打开支付宝就可以了，那么在解决区间更新的问题中，我们如何赊账呢？方法很简单，我们需要牺牲空间用来记录线段树上的每个节点是否需要更新，如果需要更新，需要更新的规则是什么。以给区间上的每个元素加一个值 x 为例，如果该节点所表示的区间需要更新，那我们就可以将对应的赊账标记记为 x ，当需要查询该区间时，对该区间进行更新，并清除赊账标记，如果该节点所表示的区间不需要更新，对应的赊账标记记为 0 。这样做的好处就在于，省去了更新无需查询区间的值，如果一次查询的过程中，只更新不查询的操作比较多，那可以料想到，节省的时间将是不可估量的。
总是赊账这么叫，看起来好 low ，其实，这个方法有个高大上的名字－－Lazy 思想，赊账标记也就叫做——Lazy Tag 。
这个想法浅显易懂，很容易就想明白了，但其发挥的作用却是无法估量的，正所谓大道至简，有时候也许就是这样浅显的道理、细微的改进效果就可以非常显著，还有时候比别人再多往前迈进一小步，就能看见另一番天地。无论是钻研问题还是生活，这个道理都同样适用。
接下来我给大家展示一下核心代码部分，希望大家看了代码能对此有更加深入的体会。
由于上篇文章中，我们介绍的线段树存储的是区间最小值，今天就以之前的假设为基础，深入研究。
以上就是今天的代码分享，发现其中有错误或者有更简洁方法的朋友可以在下方留言区留言，或者点击作者名片添加微信好友私聊，不胜感激。
还没关注公众号的朋友可以长按下方图片识别二维码关注呦。
长按二维码识别关注
代码的网页版可以打开网页http://paste.ubuntu.com/25534094/。
线段树＋rmq问题第二弹
线段树＋RMQ问题第二弹 上篇文章讲到了基于SparseTable解决RMQ问题，不知道大家还有没有印象，今天我们会从线段树的方法对RMQ问题再一次讨论。正式介绍今天解决RMQ问题的方法之前，我先对RMQ问题的概念再... 查看详情
codeforces620enewyeartree(线段树的骚操作第二弹)(代码片段)
TheNewYearholidaysareover,butReshadoesn‘twanttothrowawaytheNewYeartree.HeinvitedhisbestfriendsKerimandGuraltohelphimtoredecoratetheNewYeartree.TheNewYeartreeisanundirectedtreewith n vertices 查看详情
hduatlantis线段树表达区间
...//acm.hdu.edu.cn/showproblem.php?pid=1542我的做法是把x轴的表示为线段，然后更新y 不考虑什么优化的话，开始的时候，把他们表达成线段，并按y排序，然后第一次加入线段树的应该就是最底下那条，然后第二条的时候，我们可以询... 查看详情
线段树懒惰点标记更新hduhdu-1698justahook
...acm.hdu.edu.cn/showproblem.php?pid=1698题意：自行读题解题思想：线段树原更新一次只能更新一个叶子节点，并更新此叶子结点以上所有相关的点，当一个区间做相同更新时，叶子节点以上的相关节点不断更新，时间复杂度增加。为节省... 查看详情
liaoliao的四连做第二弹
liaoliao四连做第一弹1.bzoj3211:花神游历各国由于$10^9$以内的数最多只会被开方$10$次，所以我们可以用线段树维护然后剪枝..#include<cstdio>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>#defineLLlon 查看详情
喵哈哈村的种花魔法(线段树的区间更新)
描述喵哈哈村有一个谷歌廖，谷歌廖特别喜欢种花。而且谷歌廖最神奇的就是，他会施展一种种花魔法，会使得一定区间的花儿，长高k厘米。在谷歌廖施展若干次魔法之后，好奇的沈宝宝想知道，每朵花儿的高度是多少。输入... 查看详情
justahook线段树区间更新
JustaHook InthegameofDotA,Pudge’smeathookisactuallythemosthorriblethingformostoftheheroes.Thehookismadeupofseveralconsecutivemetallicstickswhichareofthesamelength. NowPudgewantstodosomeopera 查看详情
hdu2871线段树区间更新
不得已又挖了一个坑。。想来学习线段树也有一段时间了，也有了些了解，但是在做题的时候还是磕磕碰碰的，还是不够熟练，还是要多做题（水题除外），多思考。这是一道典型的线段树区间更新，一定要使用延迟标记，同时... 查看详情
hdu1698justahook线段树区间更新
题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=1698 题目描述：区间更新，最后求出1~n之和 解题思路：这里涉及到区间更新，这也是我第一次写区间更新，以前都是单点更新，回溯就可以了，如果将区间更... 查看详情
线段树区间更新
区间更新也可以分割成若干个子区间，每层的结点至多选取 2 个，时间复杂度 O(logn)。 懒惰（Lazy）标记懒惰标记，也可称为延迟标记。一个区间可以转化为若干个结点，每个结点设一个标记，记录这个结点被进行... 查看详情
（线段树）单点更新，区间查询最值
/*单点更新，区间查询最值*//*注意线段树的大小要比需要使用线段树的数据的个数大3到4倍*/#include<cstdio>#include<iostream>#include<algorithm>#include<cstring>usingnamespacestd;#definemaxn4000001structnode{intle,ri;int 查看详情
hdu1689justahook（线段是区间更新+区间求和）
题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=1698题意：用1，2，3三种价值的颜色去给棒子区间涂色，问最后整个棒子的价值为多少，一开始整个都涂上价值为1的颜色题解：区间更新区间求和1//HDU1689JustaHook2//区间更新区间求和... 查看详情
poj3468asimpleproblemwithintegers线段树区间更新区间查询
...行一段区间加上某一个数，和区间查询 解题思路：线段树，之前的那道题是求总区间直接输出sum[1]就可以了，这次有了区间查询，同理，查询的时候Pushdown 代码： #include<iostream>#include<cstdio> 查看详情
（转）线段树的区间更新
...dn.net/zip_fan/article/details/46775633写的很好，昨天刚刚开始写线段树，有些地方还不是很明白，看了这篇博文，学会了数组形式保存线段树，还学会了区间更新以下为转载的博文内容 距离第一次接触线段树已经一年多了，再次参... 查看详情
hihocoder#1078:线段树的区间修改(线段树区间更新板子题)
#1078:线段树的区间修改时间限制:10000ms单点时限:1000ms内存限制:256MB描述对于小Ho表现出的对线段树的理解，小Hi表示挺满意的，但是满意就够了么？于是小Hi将问题改了改，又出给了小Ho：假设货架上从左到右摆放了N种商品，并且... 查看详情
hdu3308线段树区间合并+单点更新+区间查询
LCISTimeLimit:6000/2000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):6592 AcceptedSubmission(s):2866ProblemDescriptionGivenninte 查看详情
poj3468asimpleproblemwithintegers（线段树+区间更新+区间求和）
题目链接:id=3468http://">http://poj.org/problem?id=3468ASimpleProblemwithIntegersTimeLimit: 5000MS MemoryLimit: 131072KTotalSubmissions: 83959 Accepted: 25989CaseTimeLimit:&n 查看详情
poj-3468asimpleproblemwithintegers（线段树区间更新，区间查询和）(代码片段)
YouhaveNintegers,A1,A2,...,AN.Youneedtodealwithtwokindsofoperations.Onetypeofoperationistoaddsomegivennumbertoeachnumberinagiveninterval.Theotheristoaskforthesumofnumbersinagiveninterval.InputThefirst 查看详情