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

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

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


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

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

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

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

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

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

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

什么是线段树

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

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

源码下载

[dm href=’https://www.jikewenku.com/product/1487.html’]下载地址[/dm]

导航目录

[dm href=’https://www.jikewenku.com/geeknote/2241.html’]查看导航[/dm]

本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
极客文库 » 数据结构笔记总结(8.1)什么是线段树(区间数)

Leave a Reply

欢迎加入「极客文库」,成为原创作者从这里开始!

立即加入 了解更多