分块

一，分块的基本思想

分块是一种通过将序列分块和预处理以优化暴力的思想。一般来说，分块的时间复杂度为 \(O(n\sqrt{n})\)。与其他的数据结构相比，时间复杂度更劣，但分块更加灵活便捷，适用范围更广，在很多情况下，分块就算不是正解也能拿到比较高的分数。

二，分块及其算法衍生

（1）分块

（这块实际上也属于块状数组范围，但形式不太相同。）
这部分是单纯将数组分成各个部分，使得每次操作可以针对一整个部分修改查询，提高操作效率。语言描述不够清晰，但从题目中可以明显感觉出来：

1.弹飞绵羊(https://www.luogu.com.cn/problem/P3203)

（2）块状数组

（3）块状链表

（4）树分块

（5）Sqrt Tree

(6*)莫队

<1>莫队

<2>带修莫队

<3>回滚莫队

<4>树上莫队

<5>莫队二次离线