国家集训队2005论文的集 蒋炎岩.pptVIP

CX;线段树 　　在区间统计方面，有着很大的优势： 　　区间上的最大、最小值以及它们的统 　　计、推广 平衡树 和线段树相同，在统计时有着时间上的优势，而且，与线段树最大的不同在于，平衡树不依赖于处理数据范围的大小。随着Treap等数据结构的发展，逐步在信息学奥赛中代替了难于实现的AVL和红黑树，发挥着越来越大的作用;但是;我们看国家集训队队员龙凡演讲中提到的问题 　　士兵排队;每一个整体元素是一个数组;在块状链表中间插入元素;在块状链表中删除元素;块状链表的扩张;回到问题上，块状链表正好适应了问题的要求！ 我们将带位置的数据插入到块状链表当中， 然后，假如需要移动的化，我们除了需要将某一块链中的Sqrt(n)个元素移动掉，其他的链表操作，只需要sqrt(n)的时间．Sqrt(n)完美地将复杂度平均，无论是数组，还是链表，都逃不出这个时间复杂???上限。问题至此被解决。 而且，这个算法的常数非常小，完全没有线段树等复杂的操作和分析，全部都是最简单、最基本的数据操作！;我们看国家集训队队员黄刚演讲中提到的问题 　　Dynamic Ranking;同样的，维护一个块状链表，记录所有的元素。当然，仅仅这个还是不够的：将所有的数都导入块状链表，而且，对于链表里的每一个块，都维护一个排序后的表。这个表的Replace Element仍然可以在Sqrt(n)时间内解决。然后，如黄刚同学所说，二分那个所求的最大值，然后可以轻松地扫描块，并统计出那个数是否为第k大，问题解决，时间复杂度为;看起来，这似乎比黄刚同学的算法要慢一个数量级。可是，维护平衡树和线段树的代价是很大的！;Thank You!