• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

数据结构笔记总结(8.1)什么是线段树(区间数)

极客笔记 Geekerstar 11个月前 (05-19) 442次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

为什么要使用线段树(Segment Tree)

最经典的问题:区间染色。


现在进行很多的操作:从4到9这段绘制成橙色,从7到15这段墙绘制成绿色,原来橙色的部分被最近一次的绿色给覆盖住了。

正是因为有这种覆盖情况让问题复杂了一些,继续对从1到5的这段墙绘制成蓝色,对从6到12这段墙绘制成红色。m次操作后,我们可以看见多少种颜色呢?

m次操作后,我们可以在[i,j]区间内看见多少种颜色?

显然我们完全可以使用数组来实现这个问题,如果对某一段区间进行染色,就遍历一遍这段区间改成新的颜色就好了,复杂度是O(n)级别。

如果查询这段区间相应也只需要遍历一遍就好了,复杂度也是O(n)。对于某一种数据结构如果其中某些操作是O(n)级别的话,如果我们动态的使用这种数据结构相应的性能很有可能是不够的,由于我们主要关注的是区间或者线段,相应的线段树这种数据结构就有用武之地了。

另一类经典问题:区间查询

对于一个区间内统计查询的问题,使用线段树的复杂度都是O(nlogn)

什么是线段树

给定八个元素的数组,把它构建成一个线段树(不考虑向线段树中添加或删除元素),大多数情况下对于线段树解决的问题区间本身是固定的,所以用静态数组就好了,下图所示就是一个线段树

和所有二叉树一样,它有一个个节点,不过对于线段树来说,每一个节点表示的都是一个区间内相应的信息,比如我们以使用线段树来统计区间的和为例,这样的情况下,线段树的每一个节点存储的就是一个区间的数组和,根节点存储的就是整个线段树的和。如果我们要查询某个区间的话,只需走对应的节点就行了,不需要将所有元素全遍历出来。

源码下载

下载地址

导航目录

查看导航
丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:数据结构笔记总结(8.1)什么是线段树(区间数)
喜欢 (0)
[247507792@qq.com]
分享 (0)
Geekerstar
关于作者:
本站技术支持

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00