分块思想
简介¶
其实，分块是一种思想，而不是一种数据结构。
从 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本页面贡献者：Ir1d, HeRaNO, Xeonacid
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用