现在的位置: 首页 > 综合 > 正文

离散化压缩线段树

2018年04月12日 ⁄ 综合 ⁄ 共 1418字 ⁄ 字号 评论关闭

线段树(Interval Tree)

 线段树是一种二叉搜索树,将一个大区间划分成单元区间,每个单元区间对应一个叶子节点;内部节点对应部分区间,如对于一个内部节点[a, b]而言,其左子节点表示的区间为[a, (a+b)/2],其右子节点表示的区间为[1+(a+b)/2, b];

 对于区间长度为N的线段树,由于其单元节点都是[a, a]的叶子节点,所以其叶子节点数为N,并且整棵树为平衡二叉树,所以总节点数为2N-1,树的深度为log(N)+1;

 插入操作:将一条线段[a, b]插入到区间长度为[l, r]的线段树root中,如果root不是单元节点,则求得mid=(l+r)/2;(删除和查找操作类似)

 如果b<=mid,则将[a, b]插入到root->left子树中;
 如果a=b=mid,则将[a, b]插入到root->left子树中,
 如果a=mid<b,则将[a, a]插入到root->left子树中,[a+1, b]插入到root->right子树中; 
 如果a>mid,则将[a, b]插入到root->right子树中;
 如果a<mid<b,则将[a, mid]插入到root->left子树,将[mid+1, b]插入到root->right子树中

 线段树最主要的应用是判定几个给定区间之间的关系,判定某一个区间A是否在若干个目标区间内出现,时间复杂度为O(MlogN),M为A的区间长度,N为构建线段树的整个区间长度;但原始的线段树需要表示每一个单元区间,所以空间复杂度较高为2N,优化方案是离散化(Discretization)压缩线段树区间;但是由于线段树每个节点上需要维护一个int的计数变量(记录其子树被覆盖的次数),所以每次插入或者删除操作都需要O(N)的时间维护线段树的正确性,可以为每一个节点增加一个延迟标记的delta值(Delay
Mark),这个值记录当前节点所在的区间需要进行的修改(但是还没有对其左右子树的节点进行修改),当查询路径需要到其左右子树中时,将这个delta值传递给其左右子树,而将本节点保存饿delta值去除;


 一道利用线段树的题目:给定一个自然数集合,自然数的范围是[0,30000],现在已知N条线段,每条线段以[a,b]的形式给出,现在有M个数字,要求判断每个数字分别在多少条线段上出现过;

 一般解法是将M个数字分别于N条线段比较判断,时间复杂度为O(MN);可以利用线段树记录N条线段在[0, 30000]范围内出现的次数和位置,然后利用二叉树的O(logN)查找时间判断每个数字最终出现的线段;

 首先是按照给定的元素范围构建线段树的框架;如给定[0, 7],则利用线段树为满二叉树的性质,其节点个数为2N-1=15;基本存储结构为数组,如果当前节点为array[i],则array[2*i]和array[2*i+1]分别为左右子节点;节点内拥有一个记录本节点代表的线段出现的次数,初始化为0;时间复杂度为O(logK),K为给定的区间范围;
 

 


 然后将给定的N条线段插入到已经构建好的线段树框架中;如给定三条线段:[2,5],[4,6],[0,7],依次插入则最终成为一棵可用的线段树;时间复杂度为O(NlogK)
 

 


 最后是查询给定的M个点在N条线段出现的次数;如给定数字2,则递归到线段树中的节点[2,2],并将经过的节点的count值累加起来,最终就是数字2在给定的线段集合内出现的次数;

抱歉!评论已关闭.