RainAir
My OI Blog
RainAir
线段树模板

一种快速的区间查找算法


线段树和树状数组一样,都可以在$ n log_2 n $ 的时间复杂度下求出一个动态区间的最优值。
模板一
模板二

定义

线段树是一种树形结构(这不是废话吗),它的每个结点存储的是一条线段。它是一个能在$ O(logn) $ 的时间复杂度中进行区间修改和区间查询操作的数据结构,常用于多次查询动态区间的最优值(或和)。

实现步骤

建树

我们当然是用递归构造线段树啦(这不是废话吗+1)。
我们对于一个区间,如果它的长度不为1,我们就取mid,然后将其分为两个子区间$ [l,mid] $ 和 $ [mid + 1,r] $。如果长度为1,我们就将其作为叶子节点。

Lazy-tag

显而易见,如果我们单点修改,我们只需要一直递归向上修改即可,但要对区间进行修改是,我们如果采取多次单点修改的花时间复杂度会飙升到$ O(n log_2 n) $,还不如朴素(暴力)算法。。。
看这个小标题就知道,在这里教你一种偷懒的方式,不需要那么勤奋。所以,我们可以引入Lazy-tag机制。
我们在每一个结点多去维护一个tag变量。如果我们要对区间$ [a,b] $进行统一加c操作,我们可以只先修改当前$ [a,b] $区间的值,同时我们给这个区间打上一个tag,表示该区间被整体加上了tag,方便以后查询时修正。
另外要注意在查询或修改一个结点的时候要将tag进行下方,即pushDown操作(这不是废话,这很重要!)

区间查询

当然是选择递归查询啦(这不是废话吗+2)

样例代码

代码为线段树的指针写法。
本代码以求和为基础。
实际运用时请注意数据范围。

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/101
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

线段树模板
一种快速的区间查找算法 线段树和树状数组一样,都可以在$ n log_2 n $ 的时间复杂度下求出一个动态区间的最优值。 模板一 模板二 定义 线段树是一种树形结构(这不是废话吗),它的…
扫描二维码继续阅读
2017-12-03
标签
近期评论