线段树成段更新之延迟更新

成段更新的重点是延迟更新，以区间[1,3]为例说明。

注意，此例中“更新”为修改元素的值为a，“查询”为求区间中所有元素之和。

建立二叉树如图示：

 

 

每一个圆圈代表一个结点，圆内数字分别为结点标号和所对应区间，[i]表示只含一个数，只出现在叶节点中。

 

当 要更新区间[1,2]中所有元素时，对应上图即要更新结点4,5。一种方法是依次访问结点4和5并更新，但这样时间和空间开销都较大，当要修改的区间的长 度较长时尤甚。于是可以采取“延迟更新”，即将更新信息储存在这段区间对应的结点处，此例中  [1,2]对应的区间是结点2，给结点一个属性tag用以 记录这个更新信息a，原来tag初始化为0，此时令tag = a。这样做实际上是将整一个区间[1,2]看做一个“点”，即应用单点更新。这样做的好处 是不需要更新结点4和5。而事实上，在这一步中我们也只需要知道整一个区间[1,2]的情况就足矣，如果以后每次查询都是查询整一个区间[1,2]，又何 须分别更新结点1和2？但是，存在一些情况，如查询区间[2,3]，由于上一次我们只更新了整一个区间[1,2]所对应的结点2，而没有更新结点2，此时 查询[2,3]会导致错误。此时tag起作用。要查询到结点5必须经过结点2，经过每一个结点均检查标识tag，若tag非0，表明上次没有往下执行更 新，于是执行往下更新的操作：更新1和2，然后对结点2的tag置0。

 

延迟更新的方法就是：当前父结点存储更新信息而不往下更新以减少时间可空间开销，当下次用到时再局部更新。