4.4　通过数组分块技术优化算法

如果直接在大容量的数组中进行增删元素的操作，或者计算指定子区间的最值，则效率不理想，因为增删元素需要花时间维护数组“有序性”的结构特征。例如，删除第1个元素，后面n-1个元素需要依次往前移动一个位置；再例如，将新元素插入第1个位置，n个元素需要依次往后移动一个位置，空出首位置，以便插入新元素；而计算子区间最值的效率取决于子区间的规模，子区间范围越大，顺序查找的效率越低。

为了优化算法，我们提出了一种数组分块技术。

将长度为n的数组等分成若干块，以块为单位进行块间检索。由于数组随插入操作而增大，因此块容量L取决于原数组长度n和插入操作的次数p，n和p越大，则L越大。一般来讲，数组可分成块，每块长度L=m+1。

我们可在输入数组的同时直接构造块数组，下标x的数组元素位于第块的第（x%L）个位置。如果要求区间的最值，则需要同时计算每块的最值，构造块数组的时间复杂度为O(n)。

每次插入或删除一个元素，先找到对应的块，再用O(l)时间在该块中进行插入或删除操作。每块采用动态数组，实际块长可随增删操作而变化。

如果求下标区间[x,y]的最值，则先直接计算下标x和y所在的块（O(1)）：

·若[x,y]同属一块，则需要逐一比较计算[x,y]的最值（如图4.4-1a所示）。

·若下标x和下标y分属不同的块，则需要逐一比较以x为左端的块内元素，计算首块内属于区间元素的最值；逐一比较以y为右端的块内元素，计算尾块内属于区间元素的最值；至于中间跨越的块，直接取出这些块的最值即可。最后直接比较这些块的最值，即可得出下标区间[x,y]的最值。显然，时间复杂度为O(L)（如图4.4-1b所示）。

图　4.4-1

下面，我们通过一个实例看看怎样使用数组分块技术实现序列的查询和元素插入。

【4.4.1　Big String】

给出一个字符串，请完成一些字符串的操作。

输入

输入的第一行给出初始字符串。本题设定这个字符串是非空的，它的长度不超过1 000 000。

输入的第二行给出操作指令的数目N（0<N≤2000）。接下来的N行每行给出一条指令。两种指令的格式如下。

·I ch p：将一个字符ch插在当前字符串中第p个字符之前。如果p大于字符串的长度，则将字符添加在字符串的末端。

·Q p：查询当前字符串的第p个字符。输入保证第p个字符存在。

输入中的所有字符都是数字或英文字母表中的小写字母。

输出

对每条Q指令输出一行，给出被查询的字符。

试题来源：POJ Monthly--2006.07.30,zhucheng

在线测试：POJ 2887

试题解析

如果直接在初始串上进行操作，则极有可能失败。虽然使用直接寻址方式查询的时间复杂度为O(1)，但插入操作颇为费时。插入位置越靠前，需要往后移动一个位置的元素越多，花费的时间越长，超时的风险越大。

由于操作数比较少，为了提高计算效率，可采用分块法解题。设：初始串为str[]，其长度为L，指令数为n。将初始串等分成块，每块长度l=m+1。第K块子串存储在block[K]中(1≤K≤m)，可通过语句for(int i=0;str[i];++i)block[i/l].push_back(str[i])直接将str[]中的每个字符依次放入对应的块中。

这样，每次插入前先找到对应的块，再用O(l)时间在该块中进行插入操作。查询同样需要先找到对应的块。块内的子串用动态数组实现，可以花O(l)的时间找到目标元素。如果用STL的链表来做，结果会超时。

计算效率估算如下：在最坏的情况下，一个块最多有2000个字母，最多有1000个块，当然操作不会超时。但是数组要足够大。

另外，为了快速找到当前串第pos个位置所在的串，另辟了一个块的前缀长度数组sum[]，其中sum[i]为前i块的总长度（1≤i≤Maxn）。sum[]可以直接采用递推法计算（for(int i=1;i<=Maxn;++i)sum[i]=sum[i-1]+block[i].size）。

由于sum[]是递增的，因此可以使用二分查找的库函数lower_bound()，在sum[1]…sum[Max]中直接找出第pos个位置所在的块序号p（p=lower_bound(sum+1,sum+1+Maxn,pos)-(sum)）。显然，当前串第pos个字母对应p块中第pos-sum[p-1]个字母。

参考程序