分块

前言

顾名思义

分块就是将要维护的数据分成多个块来进行操作

涉及整块的直接在块上操作

涉及块中的暴力操作

暴力即优雅

分块是在线算法

一般跟区间有关系

算法

如果一个序列长度为$n$

我们一般取$\sqrt{n}$为一个块的长度

这样块的数量也是$\sqrt{n}$

原理如下

设我们分成了$m$块 每块$n$个元素 则$mn$是一个定值 为总数量 最坏情况下 我们要遍历$m-1$个块 在最后一个块内便遍历$n-1$个元素 这样时间复杂度近似是$m+n$ 根据均值不等式 在$mn$一定的情况下 当$m=n=\sqrt{mn}$时 $m+n$才取最小值

确定好块长和块数

我们就可以将数据分块

分块操作

int block=sqrt(n); //块长
for(int i=1;i<=n;i++)
{
	belong[i]=(i-1)/block+1; //每一个位置的分组
}

然后我们就可以进行一些区间操作

比如区间更新区间查询

若区间更新横跨若干块，则只需对完全覆盖的块打上标记，对两端剩余的部分暴力更新。

和区间更新类似，区间查询时对中间跨过的整个块直接利用块存储的信息统计答案，对两端剩余的部分可以暴力扫描统计。

时间复杂度

区间修改和区间查询等操作利用线段树等数据结构也能实现，时间复杂度为$O(logn)$级别

而分块算法的时间复杂度为$O(\sqrt{n})$级别，并没有线段树等数据结构的时间复杂度优秀

但是如果遇到区间信息无法快速合并等问题

线段树就不能解决了

所以分块算法可以解决一些线段树解决不了的问题

而且线段树的常数比较大

所以有的问题分块甚至能跑过线段树

附例题

P2357 守墓人

P2801 教主的魔法

---

引用来源

分块算法详解-CSDN博客

分块算法介绍-CSDN博客

分块思想 - OI Wiki (oi-wiki.org)

侵删