跳转至

分块思想

简介

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

从 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})。

build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论