Skip to content

线段树

线段树是一种利用分支思想维护区间信息的二叉树,为了维护区间修改和区间查询的平衡,我们会分治的选择一些特殊的区间进行信息维护

什么是?

可以实现较快的区间修改和区间查询的数据结构 (logn)

为此我们需要寻找一些特殊的区间,并更新区间的信息

通常我们为了为了避免每次更新退化到 O(n) ,我们可以使用lazy标记优化区间更新过程,这样可以达到 O(logn) [1]

注释


  1. 证明的话可以从LCA角度然后缩点思考 ↩︎

网站基于vitepress主题open17💙