块状链表与块状树初步

1.块状链表的基本思想
常见的线性表结构修改操作有：再某一位置后插入一段数，从某一位置开始删除连续若干个数，我们不妨先来看看数组和链表这两种常用线性结构的实现效果。
可见，它们各有各的优势和缺点，且恰巧是优势互补。我们不禁想，如果把两者结合起来，是不是会有更优异的表现？块状链表正好是基于这个思想，将数组和链表结合了起来。块状链表整体上看其结构是一个链表，链表上每个节点存放着一段数组，链表上每个节点的数据拼接起来就是原先的整个线性表的内容，“块状”一词由此而来。
块状链表的基本组织形式，假设链表中每个节点所维护的数组的大小为S，那么，一共需要维护C快，满足SC=n(为了计算方便，如果n不是S的倍数，不妨在最后补齐相应数量的空位)，n为要维护的元素总个数。按照这种方式分块，我们来看一下块状链表在上述三种操作中的表现。
（1）定位：定位时需要沿着链表的指针依次查找。假设查询数组中第P个数，那么需要找到块Bt，使得tS<P并且（t+1)S>=P。所以，查询的时间复杂度与块数同阶，为O（C）。当然，你也许会像维护一个反向的索引，即在外部用数组维护链表节点的顺序，这样就可以二分查找了。不过由于块状链表是动态的，每次修改后这个数组又需重新维护，维护这个数组的时间复杂度仍然是O（C）。
（2）插入：插入时间显然与插入的数的个数有关，为了考察块状链表本身，我们忽略这一点。首先，需要花费O（C）的时间定位到要插入的位置，接下来插入的主要时间消耗来源于块的分裂———因为大多数情况会在块内某处插入，而分裂的时间复杂度与块的大小相关，即O（S）。
（3）删除：同样先花费O（C）的时间定位，如果整块被删除，那么只需要O（1）的时间，而块的一部分被删除的话，我们就需要把块分裂，这一步的时间复杂度同样与 块的大小相关，为O(S).
综上所述，插入与删除的时间复杂度仍然为O（S+C），SC=n,由基本不等式可知。当S=C=n的1/2的时候，S+C取得最小值。故理论上，块状链表的插入和删除操作的时间复杂度均为O（n的1/2），那么，我们如何在插入，删除等操作之后仍然保持每块大小约为n的1/2呢？以及针对于此的维护操作又有怎样的时间复杂度呢？

2.块状链表的基本操作
为了使得块状链表每次插入和删除操作的时间复杂度为理论最优值O（n的1/2），我们要保证块的大小在一定范围内。我们一般维持每个块的大小S在区间[（n的1/2）/2，n的1/2]之中，这样，块数C也在区间[n的1/2，2n的1/2]中，因此块状链表不会退化。本文中，我们采用另外一种方式来维持这种性质：保证任何相邻两块的大小加起来大于n的1/2，并且每块大小不超过n的1/2，这种方法能保证块数C在区间[n的1/2，2n的1/2]之中（简要证明：当每块大小为上限值n的1/2时，块数C取得最小值n的1/2；若任意相邻两块大小之和大于n的1/2，那么我们将所有块两两分组，即块0和块1一组，块1和块2一组…那么至多不会超过n的1/2组，又因为每组至多有两块，故总块数不会超过2n的1/2）.之所以选择这种方式，是因为考虑到代码实现的方便，因为在这种实现方式中就不需要考虑块过大而需要分裂的情形。当然，实现方式因人而异，读者可以选择适合自己的最好方式。
在介绍操作之前，我们首先对即将用到的一些变量表示做一个约定：
next域：维护链表节点的下一个位置
curSize域：维护链表节点当前数组中元素的个数
data域：维护要保存的数据。