wuvin
Always take risks!
Toggle navigation
wuvin
主页
实验室的搬砖生活
机器学习
公开的学术内容
公开的其他内容
About Me
归档
标签
友情链接
ZYQN
ihopenot
enigma_aw
hzwer
杨宗翰
关于李超树的关键细节及复杂度证明
2018-04-21 10:20:50
567
1
1
wuvin
建立一个线段树管理所有整点上的最优值。 每一个线段树节点存有一条 $X$ 轴范围和自己管理范围相同的线段，每次插入把一个插入线段拆成 $logN$ 段放入线段树内，也就是和普通线段树拆分区间一样，如果原来这个点上存有线段，则进行如下操作: * 当前线段完全在原线段上方，丢弃原线段保留当前线段。 * 当前线段完全在原线段下方，丢弃现有线段。 * 当前线段与原线段相交，交点在左儿子范围内，当前节点保留红色线段，绿色线段丢弃右半部分后往做儿子下传。  * 交点在右边的情况同理。 * 交点在中间随意采用以上两种做法之一。 所以可以得知，如果有两个线段在一个线段树节点相交，最多会造成长为$logN$一条的连续下传。由于一条线段被加入$logN$个线段树节点之中，所以单词操作复杂度最多为$O(log^2N)$。
上一篇:
SGI STL源码阅读报告
下一篇:
readMe
1
赞
567 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
1
条评论
More...
文档导航
wuvin
没有帐号? 立即注册