数列分块心得

// 此文过水，只是给自己复习的，不建议阅读

例如，在动态维护区间和的时候（虽然很多时候用线段树或者树状数组更方便），假如每块有3个属性： $add,l,r$ 。 $l$ 与 $r$ 标记了它的左端点和右端点，但 $add$ 有两种用法：

1.在查询整体和的时候使用。（李煜东的书给出的就是这种）

当要使第 $i$ 块每个元素都增加 $c$ 时，执行 $add[i]+=c$ ，然后逐一更新该块中每一项的值 $a[j]$ ，使其增加 $c$ 。// $O(1)$ 与 $O(n)$

当要查询时，如果查询该块的某部分，则逐一累加那一部分的元素然后返回；如果查询整体的和，就直接返回原始处理的 $sum$ 加上 $add[i]*len[i]$ 。// $O(n)$ 与 $O(1)$

2.查询部分元素的时候使用。

当要使第 $i$ 块每个元素都增加 $c$ 时，执行 $add[i]+=c$ ，然后把 $sum[i]$ 加上 $len[i]*c$ ；// $O(1)$ 与 $O(1)$

当要查询时，如果查询该块的某部分，则逐一累加那一部分，然后加上 $add[i]*(这一部分的长度)$ ；如果查询整体的和，直接返回 $sum[i]$ ；// $O(n)$ 与 $O(1)$

第二种方法可以在修改的时候省掉一个 $O(n)$ 。

方法不同的话，长度为 $n$ 的数列每一块的元素个数不一定是 $\sqrt{n}$ ，也不一定小于它。可能大于它。

例如，如果以李煜东书上的分块方法，给 $24$ 个元素的数列分块，每一块的元素个数分别为： $4,4,4,4,8$ 。（就因为这个原因一道题卡了很久。不过他这种方法应该是错的吧…）

留下评论