思想

把数列均等地切为若干部分,这些小的部分叫做块。从而一个对区间的询问会包含一些块和两个长度小于一个块的区间。
对于每个块,我们暴力维护它的一些信息。然后通过一些方法合并这些信息得到答案。

应用

COGS1316 数列操作b

维护数列, 支持两种操作:
1. 将 [l, r] 内的数加上 v
2. 询问 a[i] 的值
操作数小于等于 1e5

线段树当然是可以线段树的,而且时间复杂度更优。
然而分块同样可以解决这个问题,并且更好写。
维护每个块加上的值,每个数的实际值,询问时用实际值加上所在块被加上的值。
1317. 数列操作c

维护数列,支持两种操作:
1. 将 [l, r] 加上 v
2. 询问 [l, r] 中数的和
操作数小于等于 1e5

线段树当然……

维护每个块被加上的值,每个块的和,每个数的实际值。

可见,分块的想法十分简单。用分块解决问题的难点在于维护块的哪些信息,如何维护或合并这些信息来支持修改和询问。