序列分块入门教程

学妹让我教她分块,翻了翻以前的一篇博客,发现写的太难、太简略了,所以写了这篇博客 QAQ。

真的是分块最基础的教程,大佬可以跳过了。

如果本文有可以改进的地方,可以在评论区提出。

前言 - 序列分块是什么

顾名思义,序列分块就是把数列分成若干小块进行处理和维护,我们会把每一块当成整体,维护这些整体的有关信息。

最基础的分块当取块长为 n\sqrt{n} 时的初始化复杂度是 O(n)\mathcal{O}(n),单次操作复杂度是 O(n)\mathcal{O}(\sqrt{n}),当然一些较为复杂的题需要对照题目具体分析。

例题一 - P3372 【模板】线段树 1

简要分析

区间加区间和,参考题目名称可以发现,出题人貌似想让我们写线段树,于是我们考虑如何不写线段树。我们采用分块。

变量定义

以下是代码中的一些数组或变量名称及其含义:

  • n,mn,m:数列长度和操作次数。
  • aia_i:数列第 ii 项。
  • sis_i:第 ii 块所有数的和。
  • tagitag_i:第 ii 块整体加法标记,详见下文。
  • posipos_i:数列第 ii 项所在块编号。
  • LiL_i:第 ii 块左端点编号。
  • RiR_i:第 ii 块右端点编号。
  • szsz:块长。
  • tottot:总块数。

块状数组初始化

首先取块长为 n\sqrt{n},然后枚举每一块,可以知道第 ii 块的左端点是第 i1i-1 块的右端点的下一个元素,第 ii 块的右端点是 min(i×sz,n)\min(i\times sz,n),我们通过这个式子对 L,RL,R 进行初始化。

随后枚举 LiRiL_i\sim R_i 的所有元素,用 sis_i 记录他们的和,同时把这些元素的 pospos 标记为 ii

至此,我们便完成了初始化,因为每一块的区间不重叠且没有遗漏,aa 数组的每个元素下标恰好访问一遍,因此复杂度是 O(n)\mathcal{O}(n) 的。

此部分代码:

void initBlock() {
	sz = sqrt(n);
	while(++tot) {
		L[tot] = R[tot-1] + 1;
		R[tot] = min(sz*tot, n);
		rep(i, L[tot], R[tot]) pos[i] = tot, s[tot] += a[i];
		if(R[tot] == n) break;
	}
}

区间加

此部分操作要求将 axaya_x\sim a_y 的所有数加上 Δ\Delta,暴力单次加是 O(n)\mathcal{O}(n) 的,显然需要优化。

对于 xxyy 在同一块的情况,我们暴力从 xx 枚举到 yy,将 aia_isposis_{pos_{i}} 加上 Δ\Delta。由于块长为 n\sqrt{n},因此暴力枚举这一部分的复杂度为 O(n)\mathcal{O}(\sqrt{n})

对于不在同一块的情况,对两侧的零散块(不完整块,即 x,yx,y 所在块)按照同上的方法暴力处理,对中间的每个完整块记录整体加法标记 tagtag,并把块中所有数和同步记录。由于块长为 n\sqrt{n},不完整块最多操作次数为 2×n2\times\sqrt{n},完整块不超过 n\sqrt{n} 个,因此这一部分的复杂度为 O(n)\mathcal{O}(\sqrt{n})

综上,块状数组区间加法的复杂度为 O(n)\mathcal{O}(\sqrt{n})

此部分代码:

void modify(ll x, ll y, ll delta) {
	ll l = pos[x], r = pos[y];
	if(l == r) rep(i, x, y) a[i] += delta, s[l] += delta;
	else {
		rep(i, x, R[l]) a[i] += delta, s[l] += delta;
		rep(i, l+1, r-1) tag[i] += delta, s[i] += delta * (R[i] - L[i] + 1);
		rep(i, L[r], y) a[i] += delta, s[r] += delta;
	}
}

区间和

查询区间 axaya_x\sim a_y 所有数的和,同样不能暴力加,考虑按照同样的方法优化:

对于同一块的情况,暴力枚举并累加 ai+tagposia_i+tag_{pos_i}注意不要漏掉当前块的整体加法标记!

对于不在同一块的情况,两侧的零散块同样方法处理,中间的整块直接累加块和即可。

同样的,查询区间和的复杂度为 O(n)\mathcal{O}(\sqrt{n})

此部分代码:

ll query(ll x, ll y) {
	ll l = pos[x], r = pos[y], ans = 0;
	if(l == r) rep(i, x, y) ans += a[i] + tag[l];
	else {
		rep(i, x, R[l]) ans += a[i] + tag[l];
		rep(i, l+1, r-1) ans += s[i];
		rep(i, L[r], y) ans += a[i] + tag[r];
	}
	return ans;
}

AC 本题

将以上代码结合起来即可 AC 本题,总复杂度为 O(n+mn)\mathcal{O}(n+m\sqrt{n})完整代码戳我

习题一 - P2357 守墓人

基本上是双倍经验,可以稍加修改通过本题。

例题二 - P2801 教主的魔法

简要分析

简要题意:区间加,查询区间内多少个数大于等于 cc

我们可以采用分块,对每一块进行重构排序,然后询问时直接使用二分。

块内排序

块内排序在代码中用的比较多,因此我专门写了个函数重构块。

void reconstruct(int x) {
	rep(i, L[x], R[x]) b[i] = a[i];
	sort(b+L[x], b+1+R[x]);
}

初始化

初始化部分主要有一个更改:对于每一块,需要将该块内元素拷贝一遍并排序。

新初始化复杂度 O(nlogn)\mathcal{O}(n\log\sqrt{n}),使用对数换底公式可以知道这个复杂度与 O(nlogn)\mathcal{O}(n\log n) 相差为常数,可以视为 O(nlogn)\mathcal{O}(n\log n)

区间加

区间加对零散块直接暴力加,然后进行重构;因为对整块的加法不改变块内元素顺序,打上整体加法标记即可。

复杂度 O(nlogn)=O(nlogn)\mathcal{O}(\sqrt{n}\log\sqrt{n})=\mathcal{O}(\sqrt{n}\log n)

区间大于等于 cc 数个数

零散块直接暴力查询,记得加上整体加法标记。

对于完整块,在排好序的块内二分找 ctagic-tag_i,因为是排好序的,直接根据下标算即可。

复杂度 O(nlogn)=O(nlogn)\mathcal{O}(\sqrt{n}\log\sqrt{n})=\mathcal{O}(\sqrt{n}\log n)

AC 本题

结合一下以上部分即可 AC 本题,总复杂度为 O(nlogn+Qnlogn)\mathcal{O}(n\log n+Q\sqrt{n}\log n)。看到数据范围 QQ 是比较小的,可以通过。

完整代码接着戳我

习题二 - U147831 分块问题 3

区间加,求区间内 cc 的前驱。

依然是块内排序、查询时二分的思想。

习题三 - U147840 分块问题 6

单点插入,单点查询。

对于每一块维护 vector,插入时遍历每一块找插入点,查询时遍历每一块用 vector 查值即可。

这一方法可以通过本题,但是因为插入的数随机生成,每一块的插入次数大致均匀。可以通过构造数据的方式卡掉这一做法。

我选择当一块的 vector 大小超过 8×sz8\times sz 的时候将所有 vector 清空并重构,因为重构的次数比较少可以通过本题。

习题四 - P4145 上帝造题的七分钟 2 / 花神游历各国

区间开平方根,区间和。

与线段树做法想法类似,维护每一块的最小值。

习题五 - U147877 分块问题 8

查询区间内多少个数为 cc,并把区间改为 cc

经过我和几个初二学长的探讨,本题珂朵莉树解法的复杂度没有问题。

但是毕竟是练习分块,我还是老老实实地写了分块。

大致想法就是,对每一块记录区间赋值标记,优先级高于每个数的值,初始区间赋值标记设置一个特殊值表示不存在。其他的就比较基础了。

习题六 - P4168 [Violet]蒲公英

这题貌似被我咕了好久,到现在都没做。。。

先放在这里吧,有时间做完再补上(((

挑战 - 学分块怎么能不做 Ynoi 呢

写了这么多字,这部分先咕着吧,以后有时间再写(