数据结构的联合---块状链表.pdfVIP

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