单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,CX,数据结构的联合,南京市金陵中学,蒋炎岩,CX数据结构的联合南京市金陵中学 蒋炎岩,1,线段树,在区间统计方面，有着很大的优势：,区间上的最大、最小值以及它们的统,计、推广,平衡树,和线段树相同，在统计时有着时间上的优势，而且，与线段树最大的不同在于，平衡树不依赖于处理数据范围的大小。随着Treap等数据结构的发展，逐步在信息学奥赛中代替了难于实现的AVL和红黑树，发挥着越来越大的作用,线段树,2,但是,对于大数据量的修改维护、删除操作，这两种数据结,构就显得力不从心了在线段树和平衡树中，删除元、插入元素的复杂度均为O(logn)。在大量的维护面前，它们只能力不从心！,但是对于大数据量的修改维护、删除操作，这两种数据结,3,我们看国家集训队队员龙凡演讲中提到的问题,士兵排队,他用转化的思想，巧妙地解决了问题。不过我要提出的，并不是转化,问题的模型，而是直接设计一种数据结构进行维护操作，解决问题。,要快速地移动大量连续的元素，最快速的实现方法是,链表,。,要快速地定位元素，最快速的实现方法是,数组,。,为了二者效率的协调、统一，必须把它们转化，然后用树结构解决吗,?,我们可以直接把它们结合起来！,我们看国家集训队队员龙凡演讲中提到的问题他用转化的思想，巧妙,4,每一个整体元素是一个数组,数组和数组的关系是链接,从理想的角度考虑，,一个表有n个元素，,那么，理想的复杂度，,无论是插入、删除、移动,或是其他数据操作,我们的时间复杂度,都是,每一个整体元素是一个数组数组和数组的关系是链接从理想的角度考,5,在块状链表中间插入元素,在每一个块中，我们都维护一个当前表中存储数据的长度。因为数据可能插入在某一个块的中间，所以我们必须对块内的元素进行移动。当然，这可能会造成某一处的元素增加，超过Sqrt(n)。所以要在表中设置一个缓冲区，当表中元素到达2*Sqrt(n)的时候，我们把这个表断裂成两个等长的表。,在块状链表中间插入元素在每一个块中，我们都维护一个当前表中存,6,在块状链表中删除元素,与插入算法相同，某一个元素删除以后，表的长度都会减小。当相邻的两个表的长度总和小于Sqrt(n)时，我们就将这两个表合并。,在块状链表中删除元素与插入算法相同，某一个元素删除以后，表的,7,块状链表的扩张,同样的，我们可以在块状链表中加上某一个块的最大、最小值；块中的元素等，同样的，我们也可以将块状链表与其他数据结构联合。,块状链表的扩张同样的，我们可以在块状链表中加上某一个块的最大,8,回到问题上，块状链表正好适应了问题的要求！,我们将带位置的数据插入到块状链表当中，,然后，假如需要移动的化，我们除了需要将某一块链中的Sqrt(n)个元素移动掉，其他的链表操作，只需要sqrt(n)的时间Sqrt(n)完美地将复杂度平均，无论是数组，还是链表，都逃不出这个时间复杂度上限。问题至此被解决。,而且，这个算法的常数非常小，完全没有线段树等复杂的操作和分析，全部都是最简单、最基本的数据操作！,回到问题上，块状链表正好适应了问题的要求！,9,我们看国家集训队队员黄刚演讲中提到的问题,Dynamic Ranking,黄刚同学用数据结构的联合解决了这个问题。不可避免的是，线段树和平衡树的“利益”不很统一最终必须还得借助二分的帮忙。同时维护两个数据结构的代价不小，加上常数，我们不妨换一个角度考虑,块状链表,我们看国家集训队队员黄刚演讲中提到的问题黄刚同学用数据结构的,10,同样的，维护一个块状链表，记录所有的元素。当然，仅仅这个还是不够的：将所有的数都导入块状链表，而且，对于链表里的每一个块，都维护一个排序后的表。这个表的Replace Element仍然可以在Sqrt(n)时间内解决。然后，如黄刚同学所说，二分那个所求的最大值，然后可以轻松地扫描块，并统计出那个数是否为第k大，问题解决，时间复杂度为,同样的，维护一个块状链表，记录所有的元素。当然，仅仅这个还是,11,看起来，这似乎比黄刚同学的算法要慢一个数量级。可是，维护平衡树和线段树的代价是很大的！,AC就是硬道理,块状链表的出色表现说明，有时候，某个问题，并不是渐进意义复杂度小的办法，就是最好的！,看起来，这似乎比黄刚同学的算法要慢一个数量级。可是，维护平衡,12,Thank You!,Thank You!,13,