跳转至

分块思想

简介

其实,分块是一种思想,而不是一种数据结构。

从 NOIP 到 NOI 到 IOI,各种难度的分块思想都有出现。

通常的分块算法的复杂度带根号,或者其他奇怪的复杂度,而不是 \log

分块是一种很灵活的思想,几乎什么都能分块,并且不难实现。

你想写出什么数据结构就有什么,缺点是渐进意义的复杂度不够好。

当然,在 n=10^5 时,由于常数小,跟线段树可能差不多。

这不是建议你们用分块的意思,在 OI 中,可以作为一个备用方案,首选肯定是线段树等高级的数据结构。

以下通过几个例子来介绍~

区间和

动机:线段树太难写?

将序列分段,每段长度 T ,那么一共有 \frac{n}{T} 段。

维护每一段的区间和。

单点修改:显然。

区间询问:会涉及一些完整的段,和最多两个段的一部分。

完整段使用维护的信息,一部分暴力求。

复杂度 O(\frac{n}{T}+T)

区间修改:同样涉及这些东西,使用打标记和暴力修改,同样的复杂度。

T=\sqrt{n} 时,复杂度 O(\sqrt{n})

区间和 2

上一个做法的复杂度是 \Omega(1) , O(\sqrt{n})

我们在这里介绍一种 O(\sqrt{n}) - O(1) 的算法。

为了 O(1) 询问,我们可以维护各种前缀和。

然而在有修改的情况下,不方便维护,只能维护单个块内的前缀和。

以及整块作为一个单位的前缀和。

每次修改 O(T+\frac{n}{T})

询问:涉及三部分,每部分都可以直接通过前缀和得到,时间复杂度 O(1)

对询问分块

同样的问题,现在序列长度为 n ,有 m 个操作。

如果操作数量比较少,我们可以把操作记下来,在询问的时候加上这些操作的影响。

假设最多记录 T 个操作,则修改 O(1) ,询问 O(T)

T 个操作之后,重新计算前缀和, O(n)

总复杂度: O(mT+n\frac{m}{T})

T=\sqrt{n} 时,总复杂度 O(m \sqrt{n})


评论