数列分块心得

//作者过弱, 此文过水, 不建议阅读

关于标记的用法

例如,在动态维护区间和的时候(虽然很多时候用线段树或者树状数组更方便),假如每块有3个属性:add,l,rlr标记了它的左端点和右端点,但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。(就因为这个原因一道题卡了很久。不过他这种方法应该是错的吧…)

留下评论

您的电子邮箱地址不会被公开。