Appearance
线段树是一种利用分支思想维护区间信息的二叉树,为了维护区间修改和区间查询的平衡,我们会分治的选择一些特殊的区间进行信息维护
可以实现较快的区间修改和区间查询的数据结构 (logn)
为此我们需要寻找一些特殊的区间,并更新区间的信息
通常我们为了为了避免每次更新退化到 O(n) ,我们可以使用lazy标记优化区间更新过程,这样可以达到 O(logn) [1]
证明的话可以从LCA角度然后缩点思考 ↩︎