线段树的应用资源-CSDN文库

需积分: 10 110 浏览量 2011-11-15 12:07:45 上传评论收藏 172KB PDF 举报

资源推荐

资源详情

资源评论

IOI2004 国家集训队论文林涛

第 1 页共 9 页

线段树的应用

广西柳铁一中林涛

【摘要】

在竞赛解题中，常遇到与区间有关的操作，比如统计若干矩形并的面积，记

录一个区间的最值、总量，并在区间的插入、删除和修改中维护这些最值、总量。

线段树拥有良好的树形二分结构，能够高效的完成这些操作，本文将介绍

线段树的各种操作以及一些推广。

本文通过 3 个例子：《蛇》、《空心长方体》、《战场统计系统》，讲述线

段树中基本的插入、删除、查找操作，和不规则的修改和删除操作，以及到二维

的推广。

关键字：线段树二分子树收缩叶子释放面积树

【正文】

1. 线段树的定义及特征

定义 1：线段树

一棵二叉树，记为 T (a,b)，参数 a,b 表示该节点表示区间[a,b]。区间的长度

b-a 记为 L。递归定义 T[a,b]：

若 L>1 ：[a, (a+b) div 2]为 T的左儿子

[(a+b) div 2,b]为 T 的右儿子。

若L=1 ：T 为一个叶子节点。

表示区间[1, 10]的线段树表示如下：

[1,10]

[1,5]

[5,10]

[1,3]

[3,5]

[5,7]

[7,10]

[1,2]

[2,3]

[3,4]

[4,5]

[5,6]

[6,7]

[7,8]

[8,10]

[8,9]

[9,10]

(以下取对数后均向上取整)

定理 1：线段树把区间上的任意一条线段都分成不超过 2logL 条线段

证明：(1)在区间(a，b)中，对于线段(c，d)，如果(c<=a) 或 (d>=b)，那么线段在

(a，b)中被分为不超过 log(b-a)。

用归纳法证明，如果是单位区间，最多被分为一段，成立。

如果区间(a，b)的左儿子与右儿子成立，那么如果当 c<=a 时，

1．若 d<=(a+b)div2 那么相当与其左儿子分该线段，所分该线段数树不

超过 log((a+b)div 2-a)，即不超过 log(b-a),成立。

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余8页未读，立即下载

内容反馈

sfboi

粉丝: 3
资源: 51

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip