分块入门

引言

时隔很久过来填坑了。其实分块就是暴力,其本质仍是对维护信息的割裂与整合归一

线性分块

在线性结构上维护信息,我们尝试用分块处理。这种分块将结构分割为连续的几段,在维护段内的信息再整合为要查询的信息。形式化地说,我们把长度为 的序列分按每块长度为 分成 块。那么我们对每一块维护信息,在查询的时候用块的信息整合即可

【例一】区间求和

原问题如下

一个长度为 N 的序列,初始值为 ,要求支持以下两种操作:

  • 将某一区间 内的数都加 .
  • 对某一区间 求和并输出.

一道很基础的题对吧

算法分析

在复杂度描述中, 分别表示操作一和操作二的复杂度

最朴素的算法,复杂度为 .

只维护前缀和,可以做到 .

线段树或者树状数组维护,复杂度 .

我们考虑分块做法,将每 个分为一块,除了最后一个块,第 个块的元素区间为 .

维护第 个块中的每个数增加的值 ,以及每一个块的数的总和 .

修改

对于修改的区间 ,其由若干个整块和开头结尾几个残余的元素构成

对于整块,直接修改 ,同时更新 .

对于残余的元素,直接在元素上修改,同时更新 即可

复杂度 .

,那么复杂度 .

查询

对于整块,直接利用 统计.

对于残余的元素,用元素本身和 的值统计即可

复杂度 .

因此,使用分块算法的复杂度为 .

【例二】区间范围约束统计

原问题

一个长度为 N 的序列,初始值为 ,要求支持以下两种操作:

  • 将某一区间 内的数都加 .
  • 求某一区间 内数值在 之间的数的个数.

算法分析

朴素算法,排序后二分查找,复杂度 .

对此我们考虑对朴素算法做分块处理,相当于我们维护块内排序

预处理

每一个元素转化为二元组 表示该元素在块内排序前原本的位置

然后在块内对二元组按 为关键字排序

修改

维护 表示第 个块的数加的值

对于整块,直接修改 .

对于残余元素,直接在头尾的块内根据 遍历二元组并修改即可

对于头尾修改过的块,要维护其单调的性质,那么我们可以采用像归并排序一样的方式,将修改过的元素组成的序列和未修改的元素组成的序列合并,复杂度是线性的

总复杂度 .

查询

对于整块,在该块对应的区间上二分查找在区间 内的数即可

对于残余的块,遍历统计即可(要考虑

复杂度 .

那么总体复杂度 .

令分块大小 .

总体复杂度 .

【例三】区间开方

原问题

一个长度为 N 的序列,初始值为 ,要求支持以下两种操作:

  • 将某一区间 内的数都开平方,向下取整.
  • 求某一区间 内的数的和.

算法分析

求和与开平方是没有共性的,因此两者不能整合

但是这是整数开平方啊, ,开 5 次就变成 1 啦

因此我们维护一个 表示第 i 块的数是否全部变成了 1

修改

整块直接暴力开方并求和,记录在每个块的

残余的元素也暴力开方,并更新所在块的 ,遇到全部为 1 的块就可以跳过.

如果全部变成 1 了就更新 .

复杂度 .

查询

整块直接利用 求和,残余的就暴力累加

复杂度 .

由于总开方次数为 ,因此均摊下来,令 ,总复杂度 .

【例四】区间众数

一道经典分块题

一个长度为 N 的序列,初始值为 ,要求支持以下一种操作:

  • 查询区间 的最小众数

查询次数与 N 同级

算法分析

众数就是出现次数最多的数

考虑朴素算法,先对序列元素离散化

那么可以对出现次数做前缀和预处理,预处理的时空复杂度 ,查询复杂度 .

另一个算法是原地排序统计,时间复杂度 ,空间复杂度 .

算法一

尝试对第二个朴素算法分块

同样的,将元素转化为二元组 表示块内排序前的位置

然后做块内排序预处理

查询的时候,相当于我们需要对 以及残余的 个元素做归并处理,然后扫一遍统计

我们可以建一个堆维护当前待归并的元素,取出哪个块的元素就把该块下一个元素加到堆里面

做到 的查询复杂度

时,复杂度为 .(好吧其实就是常数减半)

空间复杂度 .

算法二

我们尝试维护块与块之间的信息

预处理 表示第 块到第 块的数的众数,预处理复杂度 .

对于每一个值 ,按升序记录其在序列中的位置 形成一个序列,记为 .

对于查询的区间,其众数要么就是整块的众数,要么就是残余元素的某一个值

那么我们对这 个元素 在各自的 上二分查即可知道各自在区间中的出现次数,统计即可

单次查询复杂度 ,总复杂度 .

,那么单次查询复杂度 ,多次查询总复杂度为 .

空间复杂度 .

参考文献

丁思源. 「算法笔记」分块算法. https://hydingsy.github.io/articles/algorithm-Partition/


  转载请注明: Sshwy's Blog 分块入门

 上一篇
概率与期望 ·expectation 概率与期望 ·expectation
概率的定义概率, 又称“或然率”、“几率”, 它是对一个随机事件的可能性的大小所作的数量方面的估计。 一个事件 A 出现的概率, 是 A 可能出现的情况与全部可能情况的比率。其计算公式为: P(A)=m(A 可能出现的情况)/n(所有可能的
2018.10.01
下一篇 
ZROI2018.7.27% 你赛 ZROI2018.7.27% 你赛
提高组模拟赛题面 A. 小 T 的 GCD分两个问题求解 Task1考虑到在你找到符合要求的序列后后,在其左右两边增加数字,并不会对结果有影响(多多益善)。所以直接计算整个序列的 gcd,判断是否为 1 即可。 Task2 lcm(a1.
2018.10.01
  目录