当前位置：文档之家 › 线段树与矩形切割

线段树与矩形切割

  • 格式：wps
  • 大小：337.35 KB
  • 文档页数：31

解决动态统计问题的两把利刃

——剖析线段树与矩形切割

广东北江中学 薛矛

【关键字】

线段树 矩形树 方块树 线段切割 矩形切割

【摘要】

本文从统计类型的问题出发，以更好地解决这类问题为目的，较详细地介绍

了线段树的基本操作，改进和推广；矩形切割的思想以及具体的使用方法。并通

过将线段树和矩形切割进行对比，分析了线段树和矩形切割的复杂度，优缺点等，

提出了它们各自的适用范围，并总结出何时使用最合适。

【目录】

一、引言 .................................................................................................................................... 2

二、线段树 ................................................................................................................................ 2

2.1 线段树的结构 .............................................................................................................. 2

2.2 线段树的建立 .............................................................................................................. 3

2.3 线段树中的线段插入和删除 ...................................................................................... 3

2.3.1 线段的插入 ........................................................................................................ 3

2.3.2 线段的删除 ........................................................................................................ 4

2.4 线段树的简单应用 ...................................................................................................... 4

2.5 线段树的改进 .............................................................................................................. 5

2.6 线段树的推广 .............................................................................................................. 9

2.7 线段树小结 ................................................................................................................ 10

三、矩形切割 .......................................................................................................................... 10

3.1 线段切割 .................................................................................................................... 10

3.1.1 线段的数据结构 .............................................................................................. 11

3.1.2 判断线段相交的函数 ...................................................................................... 11

3.1.3 切割线段的过程 .............................................................................................. 12

3.2 矩形切割 .................................................................................................................... 12

3.3 矩形切割的推广 ........................................................................................................ 13

3.4 矩形切割的应用 ........................................................................................................ 15

四、线段树与矩形切割的比较 .............................................................................................. 16

4.1 线段树的时空复杂度 ................................................................................................ 17

4.1.1 线段树的空间复杂度 ...................................................................................... 17

4.1.2 线段树的时间复杂度 ...................................................................................... 17

4.2矩形切割的时空复杂度 ............................................................................................. 17

4.2.1矩形切割的空间复杂度 ................................................................................... 17

4.2.2 矩形切割的时间复杂度 .................................................................................. 18

4.3 线段树与矩形切割适用范围的比较 ........................................................................ 19

五、总结 .................................................................................................................................. 19

【正文】

一、引言

我们在做练习和比赛中，经常能碰见统计类型的题目。题目通过输入数据给

程序提供事物信息，并要求程序能比较高效地求出某些时刻，某种情况下，事物

的状态是怎样的。这类问题往往比较简单明了，也能十分容易地写出模拟程序。

但较大的数据规模使得模拟往往不能满足要求。于是我们就要寻找更好的方法。

本文将介绍解决此类问题的两种方法——线段树与矩形切割。

二、线段树

线段树已经不是一个陌生的名词了，相信大家也对线段树比较熟悉，这里只

做简要的介绍。

2.1 线段树的结构

线段树是一棵二叉树，其结点是一条―线段‖——[a,b]，它的左儿子和右儿子

分别是这条线段的左半段和右半段，即[a, 2/)(ba]和[2/)(ba,b]。线段树

的叶子结点是长度为1的单位线段[a,a+1]。下图就是一棵根为[1,10]的线段树：

[8,9] [9,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]

易证一棵以[a,b]为根的线段树结点数是2*(b-a)-1。由于线段树是一棵平衡

树，因此一棵以[a,b]为根结点的线段树的深度为log2(2*(b-a))。

线段树中的结点一般采取如下数据结构：

其中a,b分别表示线段的左端点和右端点，Left，Right表示左儿子和右儿子

的编号。因此我们可以用一个一维数组来表示一棵线段树：

Tree:array[1..Maxn] of TreeNode;

a,b,Left,Right这4个域是描述一棵线段树所必须的4个量。根据实际需要，

我们可以增加其它的域，例如增加Cover域来计算该线段被覆盖的次数，bj域用

来表示结点的修改标记（后面将会提到）等等。

Type TreeNode=Record

a,b,Left,Right:Longint

End

合集下载

数长方形题目

数长方形题目

第 1 页 共 2 页 数长方形题目

（实用版）

目录

1.数长方形题目的概述

2.数长方形题目的解题思路

3.数长方形题目的解题技巧和方法

4.数长方形题目的实战演练

5.总结与展望

正文

一、数长方形题目的概述

数长方形题目是计算机算法领域中的一类经典问题，主要涉及到计算机图形学和离散数学等知识。这类题目的主要目标是计算某个区域内包含多少个长方形，通常需要对给定的数据进行分析和处理，运用一定的算法来解决问题。数长方形题目有着广泛的应用，例如在图像处理、数据统计和计算机视觉等领域。

二、数长方形题目的解题思路

解决数长方形题目的一般思路如下：

1.确定长方形的边界：首先需要确定哪些边是长方形的边界。通常，水平和垂直的边被认为是长方形的边界。

2.计算长方形的数量：根据边界，可以计算出区域内包含的长方形的数量。这一步通常需要运用离散数学中的计数原理。

3.处理重叠的长方形：在实际计算过程中，可能会出现重叠的长方形。为了解决这个问题，可以使用线段树等数据结构来记录每个长方形的边界。

三、数长方形题目的解题技巧和方法 第 2 页 共 2 页 在解决数长方形题目时，可以采用以下技巧和方法：

1.扫描线法：通过扫描线法，可以将问题转化为计算与扫描线相交的长方形数量。这种方法可以有效地减少计算量，提高算法的效率。

2.线段树：使用线段树来记录每个长方形的边界，可以方便地处理重叠的长方形，提高算法的正确性。

3.枚举法：对于一些简单的数长方形题目，可以采用枚举法来解决问题。这种方法简单直观，但只适用于题目规模较小的情况。

四、数长方形题目的实战演练

假设给定一个矩形区域，长为 4，宽为 3，内部有如下三个长方形：长为 2，宽为 1；长为 3，宽为 2；长为 1，宽为 2。请问这个区域内共有多少个长方形？

解题过程如下：

1.确定长方形的边界：水平边界为 0, 2, 4；垂直边界为 0, 1, 3。

『zkw线段树及其简单运用』

『zkw线段树及其简单运用』

『zkw线段树及其简单运⽤』

阅读本⽂前，请确保已经阅读并理解了如下两篇⽂章：

引⼊

这是⼀种由THU−zkw⼤佬发明的数据结构，本质上是经典的线段树区间划分思想，采⽤了⾃底向上的⽅式传递区间信息，避免的递归结

构，其代码相对经典线段树更简单，常数更⼩，易于实现。

统计的⼒量-源⾃。

基础⾮递归

接下来，我们将讲解zkw线段树的第⼀种实现形式，⽤于单点修改 区间查询，我们以查询区间最⼤值为例来讲解。

建树

普通线段树需要建树，zkw线段树当然也需要建树。

考虑线段树的⼀个性质，其树上的叶节点代表的往往都是形如[x,x]的元区间，⽽且除最后⼀层外，线段树是⼀颗满⼆叉树，所以我们要把这

颗线段树的数组⼤⼩先申请好了。

⼀棵满⼆叉树有x个节点时，它有x+1

2个叶⼦节点，⽽我们需要⾄少n个叶⼦节点的线段树，即使x+1

2≥n，那么我们设x=1，在x+1

2

断执⾏x∗=2，就能得到⾜够⼤⼩的线段树下标base，由于线段树的叶⼦节点可能分布在两层，所以保险起见，我们还需再将x扩⼤⼀倍，

即在x+1

得到合适的下标位置后，将1−n下标位置的原数据直接存⼊线段树的叶⼦节点即可。

其实，我们还需将下标再扩⼤两个位置，即需要保证x>n，才停⽌执⾏x∗=2。其原因是这样的：在执⾏区间查询操作时，我们需要将查

询区间[l,r]更改为(l,r)(关于原因，我们之后再分析)，才便于zkw线段树的查询，那么在询问[1,n]时，可能为调⽤到[0,n+1]的原下标，所以还

需再扩⼤两个位置。

得到了合适的下标base并将1−n的数据存⼊对应位置后，当然我们还要对1到base−1的线段树位置进⾏区间更新，这个普通的更新就可以

了。

Code:

单点修改

直接在叶节点上修改对应的值，然后更新其每⼀个⽗节点即可。

Code:inline void reset(void)

{

memset( val , 0 , sizeof val );

base = 1;

}

inline void build(int *s,int len)

POJ 题目整理

POJ 题目整理

初期:

一.基本算法:

(1)枚举. (poj1753,poj2965)

(2)贪心(poj1328,poj2109,poj2586)

(3)递归和分治法.

(4)递推.

(5)构造法.(poj3295)

(6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)

二.图算法:

(1)图的深度优先遍历和广度优先遍历.

(2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)

(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)

(3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026)

(4)拓扑排序 (poj1094)

(5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020)

(6)最大流的增广路算法(KM算法). (poj1459,poj3436)

三.数据结构.

(1)串 (poj1035,poj3080,poj1936)

(2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299)

(3)简单并查集的应用.

(4)哈希表和二分查找等高效查找法(数的Hash,串的Hash)

(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)

(5)哈夫曼树(poj3253) (6)堆

(7)trie树(静态建树、动态建树) (poj2513)

四.简单搜索

(1)深度优先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)

(2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)

(3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)

切割线定理公式及证明

切割线定理公式及证明

切割线定理公式及证明

切割线定理公式：假设$V=\{v_i\}_{i=1}^{n}$是多边形$P$的一个顶点集合，$L=\{l_i\}_{i=1}^{n}$是从$v_1$出发，从$v_i$开始绕$P$沿顺时针方向绕一圈，途经定点$v_{i+1}$与$v_i$之间的一条射线，则定理结论如下：将射线$L$在多边形$P$内部切割，给出的n段子线段的总长度T(L)与多边形面积S(P)满足：

$T(L)=2S(P)$

证明：

考虑多边形$P$包围面积S(P)中最后一个三角形，设其三个顶点分别为$v_i,v_{i+1},v_{i+2}$，以$v_i,v_{i+1}$为基线，$v_{i+2}$为外顶点。

将射线$l_i$投射到$v_i,v_{i+1}$的基线上，形成一个新的顶点$v'_{i+2}$，由$v_i,v'_{i+2}$组成的新的三角形，与原来的三角形$v_i,v_{i+1},v_{i+2}$完全相同，只不过替换了一个顶点，而新三角形的面积仍然为S(P)，且$v'_{i+2}$是射线$l_i$与多边形$P$之间的一个公共点，即射线$l_i$将多边形$P$内部切割，形成了两段新线段，令这两段新线段为$s_1$与$s_2$，则有：

$T(L)=s_1+s_2=2S(P)$

因此，得证切割线定理。