线段树
区间延迟标记:修改时仅在最表层的区间上标记。每次询问时先检查该询问区间的结点上是否有未清空的延迟标记,若有则PushDown。
常用延迟标记:add[],mul[]
例如,如图为一棵线段树:
设初始时add[1]=add[2]=……=add[13]=0。
①从根节点开始,边PushDown边向下查找(由于初始时无延迟标记,PushDown实际未执行)。找到包含于(4,7)的区间停止递归,修改其sum和add值后返回。
②向上PushUp(只修改sum)
(2)查询操作:询问(2,6)的区间和
从根节点开始,边PushDown边向下递归查找(PushDown包括修改sum和延迟标记)。找到包含于(2,6)的区间停止递归,将其sum值加入总区间和ans后返回。
(2,6)区间和:ans=0+2+9+15=26。
注意query无PushUp操作。