线段树(segment tree)

时间:2022-02-04 04:34:56

线段树在一些acm题目中经常见到,这种数据结构主要应用在计算几何和地理信息系统中。下图就为一个线段树:

(PS:可能你见过线段树的不同表示方式,但是都大同小异,根据自己的需要来建就行。)

线段树(segment tree)

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为叶子节点。

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

struct Node
{
int left,right; //区间左右值
Node *leftchild;
Node *rightchild;
};

线段树的建立:

线段树(segment tree)
Node   *build(int   l ,  int r ) //建立二叉树
{
Node *root = new Node;
root->left = l;
root->right = r; //设置结点区间
root->leftchild = NULL;
root->rightchild = NULL; if ( l +1< r )
{
int mid = (r+l) >>1;
root->leftchild = build ( l , mid ) ;
root->rightchild = build ( mid +1 , r) ;
} return root;
}
线段树(segment tree)

线段树中的线段插入和删除

增加一个cover的域来计算一条线段被覆盖的次数,因此在建立二叉树的时候应顺便把cover置0。

插入一条线段[c,d]:

线段树(segment tree)
void  Insert(int  c, int d , Node  *root )
{
if(c<= root->left&&d>= root->right)
root-> cover++;
else
{
if(c < (root->left+ root->right)/2 ) Insert (c,d, root->leftchild );
if(d > (root->left+ root->right)/2 ) Insert (c,d, root->rightchild );
}
}
线段树(segment tree)

删除一条线段[c,d]:

线段树(segment tree)
void  Delete (int c , int  d , Node  *root )
{
if(c<= root->left&&d>= root->right)
root-> cover= root-> cover-1;
else
{
if(c < (root->left+ root->right)/2 ) Delete ( c,d, root->leftchild );
if(d > (root->left+ root->right)/2 ) Delete ( c,d, root->rightchild );
}
}
线段树(segment tree)

2.线段树的运用

线段树的每个节点上往往都增加了一些其他的域。在这些域中保存了某种动态维护的信息,视不同情况而定。这些域使得线段树具有极大的灵活性,可以适应不同的需求。

例一:

桌子上零散地放着若干个盒子,桌子的后方是一堵墙。如图所示。现在从桌子的前方射来一束平行光, 把盒子的影子投射到了墙上。问影子的总宽度是多少?

线段树(segment tree)

这道题目是一个经典的模型。在这里,我们略去某些处理的步骤,直接分析重点问题,可以把题目抽象地描述如下:x轴上有若干条线段,求线段覆盖的总长度,即S1+S2的长度。

线段树(segment tree)

2.1最直接的做法:

设线段坐标范围为[min,max]。使用一个下标范围为[min,max-1]的一维数组,其中数组的第i个元素表示[i,i+1]的区间。数组元素初始化全部为0。对于每一条区间为[a,b]的线段,将[a,b]内所有对应的数组元素均设为1。最后统计数组中1的个数即可。

初始     0   0  0  0  0
[1,2] 1 0 0 0 0
[3,5] 1 0 1 1 0
[4,6] 1 0 1 1 1
[5,6] 1 0 1 1 1

其缺点是时间复杂度决定于下标范围的平方,当下标范围很大时([0,10000]),此方法效率太低。

2.2离散化的做法:

基本思想:先把所有端点坐标从小到大排序,将坐标值与其序号一一对应。这样便可以将原先的坐标值转化为序号后,对其应用前一种算法,再将最后结果转化回来得解。该方法对于线段数相对较少的情况有效。

示例:

[10000,22000]   [30300,55000]   [44000,60000]   [55000,60000]

排序得10000,22000,30300,44000,55000,60000

对应得1, 2, 3, 4, 5, 6

然后是 [1,2]     [3,5]    [4,6]    [5,6]

初始     0   0  0  0  0
[1,2] 1 0 0 0 0
[3,5] 1 0 1 1 0
[4,6] 1 0 1 1 1
[5,6] 1 0 1 1 1

10000,22000,30300,44000,55000,60000

1,       2,        3,       4,       5,       6

线段树(segment tree)

(22000-10000)+(60000-30300)=41700

此方法的时间复杂度决定于线段数的平方,对于线段数较多的情况此方法效率太低。

2.3使用线段树的做法:

给线段树每个节点增加一个域cover。cover=1表示该结点所对应的区间被完全覆盖,cover=0表示该结点所对应的区间未被完全覆盖。

如下图的线段树,添加线段[1,2][3,5][4,6]

线段树(segment tree)

插入算法:

线段树(segment tree)
void   Insert(Node  *root , int  a , int  b)
{
int m;
if( root ->cover == 0)
{ m = (root->left+ root->right)/2 ;
if (a == root->left && b == root->right)
root ->cover =1;
else if (b <= m) Insert(root->leftchild , a, b);
else if (a >= m) Insert(root->rightchild , a, b);
else
{
Insert(root->leftchild ,a, m);
Insert(root->rightchild , m, b);
}
}
}
线段树(segment tree)

统计算法:

线段树(segment tree)
int  Count(Node *root)
{
int m,n;
if (root->cover == 1)
return (root-> right - root-> left);
else if (root-> right - root-> left== 1 )return 0;
m= Count(root->leftchild);
n= Count(root->rightchild);
return m+n;
}
线段树(segment tree)

 

线段树(segment tree)的更多相关文章

  1. 『线段树 Segment Tree』

    更新了基础部分 更新了\(lazytag\)标记的讲解 线段树 Segment Tree 今天来讲一下经典的线段树. 线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间 ...

  2. 线段树&lpar;Segment Tree&rpar;(转)

    原文链接:线段树(Segment Tree) 1.概述 线段树,也叫区间树,是一个完全二叉树,它在各个节点保存一条线段(即“子数组”),因而常用于解决数列维护问题,基本能保证每个操作的复杂度为O(lg ...

  3. BZOJ&period;4695&period;最假女选手&lpar;线段树 Segment tree Beats&excl;&rpar;

    题目链接 区间取\(\max,\ \min\)并维护区间和是普通线段树无法处理的. 对于操作二,维护区间最小值\(mn\).最小值个数\(t\).严格次小值\(se\). 当\(mn\geq x\)时 ...

  4. 【数据结构系列】线段树&lpar;Segment Tree&rpar;

    一.线段树的定义 线段树,又名区间树,是一种二叉搜索树. 那么问题来了,啥是二叉搜索树呢? 对于一棵二叉树,若满足: ①它的左子树不空,则左子树上所有结点的值均小于它的根结点的值 ②若它的右子树不空, ...

  5. 浅谈线段树 Segment Tree

    众所周知,线段树是algo中很重要的一项! 一.简介 线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点. 使用线段树可以快速的查找某一个节点在 ...

  6. 线段树 Interval Tree

    一.线段树 线段树既是线段也是树,并且是一棵二叉树,每个结点是一条线段,每条线段的左右儿子线段分别是该线段的左半和右半区间,递归定义之后就是一棵线段树. 例题:给定N条线段,{[2, 5], [4, ...

  7. 线段树&lpar;I tree&rpar;

    Codeforces Round #254 (Div. 2)E题这题说的是给了一个一段连续的区间每个区间有一种颜色然后一个彩笔从L画到R每个区间的颜色都发生了 改变然后 在L和R这部分区间里所用的颜色 ...

  8. segment树&lpar;线段树&rpar;

    线段树(segment tree)是一种Binary Search Tree或者叫做ordered binary tree.对于线段树中的每一个非叶子节点[a,b],它的左子树表示的区间为[a,(a+ ...

  9. RMQ问题(线段树&plus;ST算法)

    转载自:http://kmplayer.iteye.com/blog/575725 RMQ (Range Minimum/Maximum Query)问题是指:对于长度为n的数列A,回答若干询问RMQ ...

随机推荐

  1. PostgreSQL-PL&sol;pgSQL

    参考: https://wiki.postgresql.org/wiki/9.1%E7%AC%AC%E4%B8%89%E5%8D%81%E4%B9%9D%E7%AB%A0 摘记: PL/pgSQL是 ...

  2. C语言初级进阶1

    1.数据类型1.1.基本数据类型数据类型分2类:基本数据类型+复合类型基本类型:char short int long float double复合类型:数组 结构体 共用体 类(C语言没有类,C++ ...

  3. 朝花夕拾-android 获取当前手机的内存卡状态和网络连接状态

    序言: 人的一生是一个选择的过程. 如果脚下只有一条路,只要一往无前即可,不用担心走错.即使是错也别无它法.然而人是不安分的,况且安于独木桥的行走,其目的地由于没有蜿蜒曲折去遮挡行路人的视线,一往无前 ...

  4. Java之美&lbrack;从菜鸟到高手演练&rsqb;之JDK动态代理的实现及原理

    Java之美[从菜鸟到高手演练]之JDK动态代理的实现及原理 JDK动态代理的实现及原理 作者:二青 邮箱:xtfggef@gmail.com     微博:http://weibo.com/xtfg ...

  5. 《linux源代码包的编译安装》RHEL6

    linux下源代码包的编译安装其实没那么复杂. 我是win7系统装的虚拟机,就简单说下: 举个简单的例子: http://www.openssl.org/ 这是openssl的官网,下载openssl ...

  6. nfs&colon;server 172&period;168&period;1&period;22 not responding&comma;still trying问题解决方法 平台为RealARM 210平台

    nfs:server 172.168.1.22 not responding,still trying问题解决方法 ,平台为RealARM 210平台. 这里的问题是在使用nfs挂载文件系统时遇到的, ...

  7. python学习第十五天 -面向对象之继承和多态

    大家都知道面向对象的三大特性:封装,继承,多态.封装特性在上一章节已经讲解过.这一章节主要讲解继承和多态. 继承: 当定义一个类的时候,可以从现有的类进行继承.那么新定义的类可以称为子类,被继承的现有 ...

  8. SQL SERVER递归查询

    SQL SERVER 进行递归查询 有如下数据表

  9. sql定时自动备份&lpar;定时作业&rpar;

    第一步: 右键启动"SQL Server 代理"

  10. Java探秘之神秘的字符串String&lpar;二&rpar;

    不可变性 String可以说是最常用的类型了,即字符串类型,String是常量(final关键词修饰的),他的值不能被创建后更改,因为字符串是不可被改变的,所以可以被用来共享. Java语言为Stri ...