没有合适的资源？快使用搜索试试~ 我知道了~

文库首页课程资源讲义线段树入门

线段树入门

需积分: 10 2 下载量 80 浏览量 2015-08-05 15:58:00 上传评论 1 收藏 349KB PPT 举报

温馨提示

试读

39页

线段树入门资料，有利于初学者学习，让他们详细了解线段树。

资源推荐

资源详情

资源评论

线段树入门

——

长乐市第一中学

郑豪

(Platina)





线段树是建立在线段的基础上，每个结点

都代表了一条线段

[a , b]

。长度为

的线段成

为元线段。非元线段都有两个子结点，左结点

代表的线段为

[a , (a + b ) / 2]

，右结点代表

的线段为

[( a + b ) / 2+1 , b]

。

线段树的定义



线段

[1, 9]

的线段树

[1,9]

[1,4] [5,9]

[1,2] [3,4] [5,6] [7,9]

[8,9]1 2 3 4 5 6 7

8 9

性质



每层都是

[a,b]

的划分

记

L=b-a,

则共

log

层



任两个结点要么是包含关系要么没有公共部分

不可能部分重叠



给定一个

叶子

从根到

路径上所有结点

(

即

的所有

直系祖先

)

代表的区间都包含点

且

其他结点代表的区间都不包含点



给定一个区间

[l, r],

可以把它分解为不超过

2log

条

不相交线段的并

应用：求区间最值



现有

个元素组成的数列（

n<=100000

），

有

个询问（

m<=100000

），每次询问

区间

[l,r]

中的最大最小值。

剩余38页未读，继续阅读

评论收藏

内容反馈

资源评论

资源反馈

评论星级较低，若资源使用遇到问题可联系上传者，3个工作日内问题未解决可申请退款~

ACist_HQ

粉丝: 2

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

线段树入门

算法艺术-线段树入门

线段树入门讲义（PPT）

线段树 入门 总结 Interval Tree

细讲线段树

线段树入门学习(二）(兼解POJ3468) JAVA

线段树(一)

线段树（1）

线段树入门学习(兼解HDU1754)

线段树入门学习(三）懒操作(兼解POJ1823) JAVA

权值线段树和主席树入门

轻松学习线段树 进来看看

线段树和树状数组入门介绍

线段树

线段树题目

线段树函数

线段树的讲义

遍历线段树

线段树+入门+总结+Interval+Tree.rar_algorithm_interval tree_ponyj9e_tree

Lmne.rar_数值算法/人工智能

高级数据结构入门知识

算法竞赛入门经典--训练指南，代码仓库

算法竞赛入门经典--训练指南，代码仓库最新版

线段树_线段树_

线段树算法

线段树(二)

线段树代码

线段树.pptx

如何查找技术资料----我的一点心得体会

「我在淘天做技术」智能对话新纪元：百万日活对话机器人的 LLM 落地实践

最新资源

线段树入门总结 Interval Tree

轻松学习线段树进来看看