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