——《高级数据结构》
操作1：
合并Merge(curBlock,nextBlock)
该操作的目的是将相邻两个块合并。一般当相邻两个块的大小加起来不超过n的1/2的时候需要进行合并操作。这一步将nextBlock合并给curBlock，其伪代码如下：
function Merge(curBlock,nextBlock)
{
memcpy(data[curBlock]+curSize[curBlock],data[nextBlock],curSize[nextBlock])
//复制数据到当前块
curSize[curBlock]<-curSize[curBlock]+curSize[nextBlock]
next[curBlock]=next[nextBlock]
DeleteBlock(nextBlock)//删除链表节点释放内存
上述操作花费的主要时间来自于数据的复制，单次合并的时间复杂度为O(n)。有了合并操作，我们来定义维持块状链表不褪化的维护操作。
}
操作2：MaintainList()
不难想到维护的方式：在每次块状链表结构改变之后执行维护操作。顺序扫描链表结构，没碰到相邻两块的大小满足合并条件就将其合并，如此反复直到扫描到链表末端。其伪代码如下：
function MaintainList()
curBlock<-List_head//将指针置于链表表头
while (curBlock!=null)
{ nextBlock<-next[curBlock]
while (nextBlock!=null&&curSize[curBlock]+curSize[nextBlock]<=n的1/2)
{
Merge(curBlock,nextBlock);
nextBlock<-nextBlock[curBlock]
}
curBlock=next[curBlock]
}
由于插入和删除的方式特点，使得每次需要维护的块数较少，再加上线性扫描整个链表的时间，一次维护的时间复杂度仍然为O（n的1/2）。
有了维护操作，我们便可以修改块状链表来使得它不退化了。在定义插入和删除操作之前我们先定义更基本的一个操作——分裂。
操作3：分裂 split(curBlock,pos）
该操作是将块状链表中原来的curBlock这一块从pos处分裂为两块（注意pos是快内存的位置而不是全局的位置）。分裂操在其他大多数操作中都会用到，最重要的作用是取出我们所要操作的区间，在后文中会详细介绍。
分裂操作的代码如下：
```
function split(curBlock,pos)
{
if (pos==curSize[curBlock]) return//分裂的位置在末尾，不需要分裂
newBlock<-GetNewBlock()//新建一个链表节点
next[newBlock]<-next[curBlock]
curSize[newBlock]<-curSize[curBlock]-pos
memcpy(data[newBlock],data[curBlock]+pos,curSize[newBlock])
//将原来块的后半部分数据复制给新块
next[curBlock]<-newBlock
curSize[curBlock]<-pos//调整原来块的大小
上述操作花费的主要时间来自于数据的复制，单次分裂的时间复杂度为O（n）.
有了分裂操作，我们便可以来定义插入和删除操作了。
}
```
操作4 插入：Insert(pos,num,str)
该操作的意义是在块状链表的pos处插入num个数，其中待插入的数据为str，我们首先获得一个直观的概念：首先找到位置将原块分裂，然后我们将待插入的数据组织成最紧凑的形式，即前面若干个大小为O（n的1/2）的块最后添上一个余项（块）的形式，插入到原块状链表中。至此，我们完成了插入操作。下面给出插入操作的伪代码：
function Insert(pos,num,str)
{
curBlock<-GetBlock(pos)//获取pos指向的块的编号，同时pos改变为快内位置
Split(curPos,pos)//进行分裂操作
curNum<-0
while(curNum+BLOCK_SIZE<=num) do{
newBlock<-GetNewBlock()
Set data of new Block //设置新块的数据，维护链表后继指针，这里不再赘述
curBlock<-newBlock
curNum<-curNum+n的1/2
End while
if (num-curNum!=0）
newBlock<-GetNewBlock()
Set data of new Block
MaintainList() //执行维护操作
}
}
操作5 删除 Erase(pos,num)
该操作的意义是在块状链表中删除从pos处开始的num个数。我们首先找到这两个“关键点”，下一步，我们就可以通过分裂操作取出这一段区间了，接下来只需要简单地执行链表的删除操作即可。下面给出删除操作的伪代码：
function Erase(pos,num)
{
curBlock<-GetCurBlock(pos)
split(curBlock,pos)
nextBlock<-next[curBlock]
while (nextBlock!=-1&&num>curSize[nextBlock])
{
num<-num-curSize[nextBlock]
nextBlock<-next[nextBlock]
}
split(nextBlock,num)
nextBlock<-next[nextBlock]
p<-next[curBlock]
while (p!=nextBlock) {
next[curBlock]<-next[p]
DeleteBlock(p)
p<-next[curBlock]
}
MaintainList()
}
至此，我们介绍完了块状链表的一些基本操作。
块状链表的扩张
上面介绍了块状链表的一些基本操作，但是再实际应用中碰到的情形往往不会这么简单，对高级数据结构有所研究的读者一定会碰到诸如维护区间和，区间最大值等一系列问题，常用的数据结构有线段树，平衡树等。现在，我们通过给块状链表维护额外的域对其扩张，使得它同样可以应付这一类问题。同时，我们将看到块状链表的其他表现以及相比较其他数据结构的优越之处。
1.维护区间和以及区间最值
常见的问题形式为：维护两种操作，一是修改（将某处的值增加一个量）；二是询问（询问某个区间的和）。用块状链表维护这类问题的时候，我们给每个块新增加一个sum域代表该块对应的综合。
对于修改，由于只修改一处，我们仅需要对将要被修改的块的和做相应的修改，时间复杂度为定位的复杂度，即O（n的1/2）
对于查询，在上文中我们提到过，可以用分裂操作提取出我们要操作的区间。注意分裂操作过程中需要对sum域进行相应的修改，修改的方法很简单，只需要依次枚举分裂后快内每个元素，累加进sum域即可。由于块的大小为n的1/2，所以查询的时间复杂度同样为O（n的1/2），综上所述，每次操作的时间复杂度为O（n的1/2）.
用类似的方式，我们还可以维护区间的最大值，最小值等一些有用的信息。
如果修改的数不是一个数，而是一个区间那？我们可以再额外增加一个delta域，代表该块被修改的增量.修改区间的时候，如果是整块被修改，那么只需要将该块的delta域修改即可；如果是块的一部分被修改，由于块的大小不超过n的1/2，并且这种局部修改的块数不会超过两块（至多为提取出的首位两块），故可以逐一修改。所以，如果修改的是一个区间，我们同样可以再O（n的1/2）的时间内解决。
因此，我们可以小结一下以上分析得到的经验：
(1）提取一个区间可以用分裂操作
（2）：修改的时候如果是整块的修改，那么再额外的域中记录相应的信息；如果是块的一部分被修改，，那么可以逐一修改
2.维护局部数据有序化
通常，数据的有序化能够给我们处理问题带来许多便利。有了上述经验，我们不难想到维护方法——首先，块内数据用一般的排序算法维持其有序；如果修改是针对整块的，同样对delta域进行修改，否则对块内数据逐一修改再重新排序。这样，单次操作的时间复杂度为排序的时间复杂度。如果用一般的快速排序，那么单次操作的时间复杂度仍然为O（n的1/2*log2(n的1/2)）
3.维护区间翻转
由于有链表这种可以灵活变化的结构存在，使得区间的翻转也不是难事。第一步，我们同样通过分裂操作取出待翻转的区间。接下来，我们通过改变链表的next域使得链表节点顺序反序。块内数组的顺序我们不能逐一修改，所以通过额外维护的域reversed代表该块有没有被翻转，单次翻转的时间复杂度仍然为O（n的1/2）.
还有许多于具体问题相关的维护技巧，可以通过平时的联系来不断积累。掌握好块状链表的分裂操作以及对额外域的维护，便不难应对多变的问题了。
4。块状链表于其他数据结构的比较
上面提到的许多操作相信会想到用一些线段树或者平衡树处理的方法，那么块状链表与这些数据结构相比较会有什么优势呢？
(1)易于支持序列操作。块状链表的基本操作中就有序列的插入，删除，并且也易于支持序列翻转等操作。但是，如果用线段树或者平衡树来解决序列的插入，删除，翻转等操作的话，其编程复杂度以及思维复杂度和之前不用维护这些操作的时候相比上升了几个台阶。所以，简而言之，块状链表具有相对较低的编程复杂度以及思维复杂度。
（2）较小的时间复杂度系数。虽然对于常见的维护操作，用块状链表的单次操作时间复杂度通常为O(n的1/2)，而用线段树或平衡树维护，其时间复杂度通常为O（log2n）,但是块状链表的操作非常简洁，O（n的1/2）的时间通常花费在简单的循环或者数据的复制上，而诸如功能非常强大的Splay等数据结构，其较大的复杂度常数因子使得在解决实际问题的效率上未必会比块状链表更优秀。
5 分块思想在树上的应用——块状树
通过以上对块状链表的介绍，读者们会发现，块状链表的精髓在于其“分块”思想。或者更一般地说，是其“分而治之”的思想————通过将原问题划分为较小的几个部分，然后，每个部分可以用一种更简单，更直观的方法处理，最后通过高效的方式组合这些处理结果。
我们来看一下这种分块的思想应用到树中会有怎样的效果。在本章讨论的问题中，我们暂时不考虑树的结构变化，即不考虑树边的删除，添加操作，在之后的章节中会有更优秀的数据结构支持这样的操作。我们只考虑将分块思想应用于树中的查询，修改操作，
考虑以下一个实际的问题，对于一棵树维护两种操作。
（1）查询：询问树中两点之间路径上边权的最大值
（2）修改：修改某一条边的权值
朴素的操作对于修改有着O（1）的时间复杂度，不过对于查询需要O（n）的时间。优化势在必行，我们借鉴块状链表分块的思想，对树分块——将树分为n的1/2个块，每块是一个联通分量，其大小不超过n的1/2，下面，我们来看看如何将上述两种操作的时间复杂度维持在O（n的1/2）.
对于查询，经过这样的分块之后，不难发现，任意两个节点之间的路径所经过的块数不会超过O（n的1/2）.我们给每个节点维护这样一个值：到其所在块的根节点路径上边权的最大值。这样，只要通过被查询的节点不断向上查询祖先，直到找到它们的最近公共祖先为止，便得到了答案。
对于修改，由于修改只会影响一个块的内容，所以我们可以对整个块重新计算其中每个节点到块根节点的边权最大值。一个简单的优化是只修改块中被影响的子树。
最后，我们还需要解决分块的问题——分块的方法有很多，我们可以按照深度优先或者宽度优先的顺序遍历树，贪心合并节点到一个块中（即能合并就合并，直到该块的大小超过n的1/2为止）
虽然上述块状树能够处理的操作比较少，不过由于其实现非常简单，并且在一些需要更高级的数据结构，例如树链剖分等维护的情况下，能够作为一种“经济”的替代品。d
京公网安备 11010502036488号