欢迎来到天天文库
浏览记录
ID:56386153
大小:154.00 KB
页数:15页
时间:2020-06-14
《线段树的基础应用.ppt》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、线段树的基础应用---lostcows解题报告AngelClover模型:有一个未知排列。已知排列中元素个数以及每个元素前面有多少个元素比它本身小。求此排列。思考:如果我们从前面考虑每个给出的数字的话。当前这个数字只代表了它和它前面的元素的关系。我们能不能把它转化为对一个已知整体的考虑呢?显然是可以的。如果我们从后向前看。每一个剩下的局部都是一个可以已知的整体。于是,此时的Ki+1代表的就是此元素在整个集合中的位置。当我们每确定一个元素的时候,就把它从原有集合中拿出来。于是剩下的集合又可以继续刚才的过程。我们怎么实现在一个集合中查找第K大数而且还要支持
2、动态删除点呢。朴素算法显然是可以的。但是我们需要更高效的算法。于是,线段树就出场了。。。。样例:于是,排列就自动倒着出现了….Thanks
此文档下载收益归作者所有