已迁往:
http://www.wypblog.com/archives/144一、线段树基本概念
线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。
对于线段树中的每一个非叶子节点[a,b],它的左儿子表示的区间为[a,(a+b)/2],右儿子表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树,最后的子节点数目为N,即整个线段区间的长度。
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为O(logN)。而未优化的空间复杂度为2N,因此有时需要离散化让空间压缩。
性质:父亲的区间是[a,b],(c=(a+b)/2)左儿子的区间是[a,c],右儿子的区间是[c+1,b],线段树需要的空间为数组大小的四倍
二、线段树的存储数据结构
由上面的图可以看出,存储一颗线段树和二叉树有点类似,需要左孩子和右孩子节点,另外,为了存储每条线段出现的次数,所以一般会加上计数的元素,其具体如下:
struct Node // 线段树
{
int left;
int right;
int counter;
}segTree[4*BORDER];
其中,;left代表左端点、right代表右端点,counter代表每条线段出现的次数,BORDE代表线段端点坐标不超过100。由上面的性质可以知道,我们需要4倍的空间来存储。
三、线段树支持的操作
一颗线段树至少支持以下四个操作:
- void construct(int index, int lef, int rig),构建线段树 根节点开始构建区间[lef,rig]的线段树
- void insert(int index, int start, int end),插入线段[start,end]到线段树, 同时计数区间次数
- int query(int index, int x),查询点x的出现次数,从根节点开始到[x,x]叶子的这条路径中所有点计数相加方为x出现次数
- void delete_ (int c , int d, int index),从线段树中删除线段[c,d]
具体操作如下:
1、线段树的创建
/* 构建线段树 根节点开始构建区间[lef,rig]的线段树*/
void construct(int index, int lef, int rig)
{
segTree[index].left = lef;
segTree[index].right = rig;
if(lef == rig) // 叶节点
{
segTree[index].counter = 0;
return;
}
int mid = (lef+rig) >> 1;
construct((index<<1)+1, lef, mid);
construct((index<<1)+2, mid+1, rig);
segTree[index].counter = 0;
}
2、线段树的元素插入
/* 插入线段[start,end]到线段树, 同时计数区间次数 */
void insert(int index, int start, int end)
{
if(segTree[index].left == start && segTree[index].right == end)
{
++segTree[index].counter;
return;
}
int mid = (segTree[index].left + segTree[index].right) >> 1;
if(end <= mid)//左子树
{
insert((index<<1)+1, start, end);
}else if(start > mid)//右子树
{
insert((index<<1)+2, start, end);
}else//分开来了
{
insert((index<<1)+1, start, mid);
insert((index<<1)+2, mid+1, end);
}
}
3、线段树的元素查找
/* 查询点x的出现次数
* 从根节点开始到[x,x]叶子的这条路径中所有点计数相加方为x出现次数
*/
int query(int index, int x)
{
if(segTree[index].left == segTree[index].right) // 走到叶子,返回
{
return segTree[index].counter;
}
int mid = (segTree[index].left+segTree[index].right) >> 1;
if(x <= mid)
{
return segTree[index].counter + query((index<<1)+1,x);
}
return segTree[index].counter + query((index<<1)+2,x);
}
4、线段树的元素删除
void delete_ (int c , int d, int index)
{
if(c <= segTree[index].left && d >= segTree[index].right)
segTree[index].counter--;
else
{
if(c < (segTree[index].left + segTree[index].right)/2 ) delete_( c,d, segTree[index].left);
if(d > (segTree[index].left + segTree[index].right)/2 ) delete_( c,d, segTree[index].right);
}
}
四、线段树的应用
- 区间最值查询问题
- 连续区间修改或者单节点更新的动态查询问题
-
多维空间的动态查询
(转载请注明:http://www.wypblog.com/archives/144,请不要用于商业目的。)
分享到:
相关推荐
acm中的基本常用数据结构:线段树的基本题型介绍,大家一起学习进步
北京大学暑期ACM课程资源,留作备份.。
线段树 树状数组 数据结构 线段树 树状数组 数据结构 acm 线段树 树状数组 数据结构 线段树 树状数组 数据结构 acm 线段树 树状数组 数据结构 线段树 树状数组 数据结构 acm 线段树 树状数组 数据结构 线段树 树状...
线段树点更新
信息学数据结构之线段树,十分的全面,代码,ppt,讲义,一应俱全。
线段树(Segment Tree)是一种强大的数据结构,特别适用于处理区间查询和更新问题。本资源不仅提供了线段树的基础模板,还特别包含了线段树乘法操作的实现,进一步扩展了线段树的应用范围。 核心特性: 基础与进阶...
算法-数据结构- 线段树.rar
线段树 c语言 数据结构 c++ ppt
线段树模板,采用二叉结构储存数据。适用于区间及点的修改与查询操做。是一种灵活性较大的数据结构。
线段树 数据结构课程设计 除了初始化 插入 删除 还有统计部分 区间分解 数字查找
线段树,数据结构,极其一般的方法 线段树,数据结构,极其一般的方法 线段树,数据结构,极其一般的方法
线段树 数据结构 数 统计 RMQ 可以动态查询和添加
数据结构之线段数,是学习的好东东的,看看把,很好的
数据结构的选择 线性结构 树形结构 的算法讲解和题型分析
针对线段树的四道c++习题
线段树拥有良好的树形二分结构,能够高效的完成这些 线段树的各种操作以及一些推广。 本文通过 3 个例子: 《蛇》 、 《空心长方体》 、 《战场 段树中基本的插入、删除、查找操作,和不规则的修改和删 的推广
线段树(Segment Tree)是一种高效且广泛应用的数据结构,它在处理区间查询和更新问题时表现出色。本资源提供了一个完整的线段树基础模板,旨在帮助开发者快速掌握并应用线段树解决实际问题。 特点: 基础性:适合...
下图就是一棵根为[1,10]的线段树: 易证一棵以[a,b]为根的线段树结点数是2*(b-a)-1。由于线段树是一棵平衡树,因此一棵以[a,b]为根结点的线段树的深度为log2(2*(b-a))。 线段树中的结点一般采取如下数据...
ACM数据结构之树状数组和线段树 ACM数据结构之树状数组和线段树 ACM数据结构之树状数组和线段树
线段树就是可以解决这类问题的数据结构 举例说明:已知线段[2,5] [4,6] [0,7];求点2,4,7分别出现了多少次 在[0,7]区间上建立一棵满二叉树:(为了和已知线段区别,用【】表示线段树中的线段) 【0,7】 / \ 【0,3...