分块

定义

• 把一个序列从左往右切分成若干块，每块大小不超过size。
• 一个区间可以看作是若干个完整的块加上两端零碎的不超过2size个数。
• 对于每个完整的块维护信息方便修改/查询。 ## 例子

分块思想 - 例子

• 假设块大小size=4，则序列划分为：
• [1 2 3 4] [5 6 7 8] [9 10 11 12] [13 14]
• 区间[3,13]为：
• [1 2 3 4] [5 6 7 8] [9 10 11 12] [13 14]

预处理

计算出每一个节点的块起点和终点

a[1..n]
x -> x>>K
int st[(N>>K)+5],en[(N>>K)+5];
for(i=1;i<=n;i++)en[i>>K]=i;
for(i=n;i;i--)st[i>>K]=i;

例题1——最大值

单点修改求块内最大值

分块维护区间信息

• 两种操作：单点修改，查询区间最大值。
• 每块记录该块元素的最大值val。
• 修改：暴力遍历被修改元素所在的块，找到最大值作为该块的val，时间复杂度O(size)。
• 查询：对于完整的块用val更新答案，对于零碎的两块暴力遍历其中所有元素得到答案。
• 时间复杂度O(size+n/size)，当size=sqrt(n)时取得最小值O(sqrt(n))。

零碎部分进行循环遍历得到最大值

单点修改+区间和

快速修改

分块数据结构 - 高效修改

• 两种操作：单点加k，查询区间和。
• 每块记录该块元素的和sum。
• 修改：将所在块的sum+=k，时间复杂度O(1)。
• 查询：对于完整的块用sum更新答案，对于零碎的两块暴力遍历其中所有元素得到答案。时间复杂度O(sqrt(n))。

快速查询

维护前缀和数组可以加速查询

分块数据结构 - 高效查询

• 两种操作：单点加k，查询区间和。
• 令s[i]=a[1]+a[2]+…+a[i]，则[1,r]的和=s[r]-s[1-1]，考虑如何快速求出某个s[i]。
• 分块，每块记录该块所有s都加上了多少(tag)。
• 修改：将所在块对应的s都加上k，并将后面每个块的tag都加上k，时间复杂度O(sqrt(n))。

s[x..n]+=k
m=n>>K;
[0..m]

......|......|.x..|......|......|......|...

tag[i]
for(i=en[x>>K];i>=x;i--)s[i]+=k;
for(i=(x>>K)+1;i<=m;i++)tag[i]+=k;
修改：O(size+n/size)

x -> s[x]?

int ask(int x){
    return s[x]+tag[x>>K];
}
O(1)

例题1 - 区间众数

例1-区间众数

• 首先离散化a数组，使得1 <= a[i] <= n。
• 分块，预处理出f[i][j]表示第i块到第j块的众数。
• 对于一个查询[l,r]，令x和y为l和r所在块。
• 如果x==y或者x+1==y，那么区间长度不大，暴力即可。
• 否则先令ans=f[x+1][y-1]，那么只需要考虑l和r所在块的数作为众数的情况。
• 暴力枚举零碎的不超过2size个数即可。

代码

1 f[i][j]
2 // 第[i..j]块的众数
3 
4 [0..m]
5 st[i]
6 en[i]
7 for(i = 0; i <= m; i++) {
8     // f[i][i] f[i][i+1] f[i][i+2] f[i][i+3]... f[i][m]
9     tmp = 0;
10    for(k = 1; k <= n; k++) cnt[k] = 0;
11    for(j = i; j <= m; j++) {
12        // f[i][j]
13        for(k = st[j]; k <= en[j]; k++) {
14            up(tmp, ++cnt[a[k]]);
15        }
16        f[i][j] = tmp;
17    }
18 }
19 O(n / size * n) = O(n^2 / size)

暴力：

int ask(int l, int r) {
    int L = l >> K, R = r >> K, ans = 0;
    if (L + 1 > R) {
        for (int i = l; i <= r; i++) up(ans, ++cnt[a[i]]);
        for (int i = l; i <= r; i++) cnt[a[i]] = 0;
        return ans;
    }
}

全部解法

例1-区间众数

• 如何快速求出数字k在[1,r]的出现次数？

• 用临时数组cnt[i]记录数字i在零碎的部分的出现次数。

• 那么k的出现次数=cnt[k]+k在第[x+1,y-1]块的出现次数。

• 预处理g[i][j]表示前i块中数字j的出现次数。

• 则k的出现次数=cnt[k]+g[y-1][k]-g[x][k]，时间复杂度O(1)。

• 块大小为size，一共n/size块。

• 预处理：先枚举i，然后从i往右依次加入每个数更新众数，时间复杂度O(n/size*n)=O(n^2/size)。

• 查询：需要枚举零碎的数，时间复杂度O(size)。

• 总时间复杂度O(n^2/size+m*size)，当size=sqrt(n)时取得最小值O((n+m)sqrt(n))。

例题2 - 第k小

例2-区间第k小

• 给定一个序列a[1..n]。
• m次操作，要么把某个区间所有数加上k，要么查询某个区间的第k小值。

解法（暴力

• 分块，将每块内的所有数字从小到大排序。

• 对于每一块，额外记录tag[i]表示第i块所有数都加上了多少。

• 修改：将被覆盖的完整的块的tag都加上k；暴力修改两端零碎的元素的值，并将零碎的两块重新排序。

• 修改的时间复杂度：O(n/size + size*(n))。

• 查询：二分答案ans，统计有多少个数字不超过ans，假设有cnt个数字不超过ans，如果cnt<k则说明答案偏小。

• 如何统计有多少个数字不超过ans？

• 对于零碎的两块暴力扫描所有数字进行统计；对于完整的块在有序数组中二分查找即可。

• 修改：O(n/size+size*log(n))。

• 查询：O(log(v)*(size+n/size*log(n)))。

• 当size=sqrt(n*log(n))时取得最小值O(log(v)*sqrt(n*log(n)))。

优化算法

修改

区间第k小 - 优化

• 修改：对于零碎的两块，每块都是一部分数加上了k而另一部分数不变。
• 可以将这两部分数分别从之前的排序结果中抽取出来，记为f和g。
• 将f加上k后和g进行归并即可得到新的排序结果。
• 时间复杂度O(size+n/size)。

查询

• 查询：对于零碎的两块，可以将需要的数字从排序结果中抽取出来，那么我们就得到了两个临时的完整的块。
• 二分答案后，此时只需要在每个完整的块中二分查找即可。
• 时间复杂度O((v)*n/size*(n))。

复杂度

• 修改：O(n/size + size)。
• 查询：O((v) * n/size * (n))。
• 当size = * (n)时取得最小值O((v) * )。

分块及其灵活

例题3 - 子序列

• 给定一个序列a[1..n]。
• 问有多少个长度至少为2的子序列b[1..m]，满足将每个数在二进制下看作集合后，b[i]是b[i - 1]的子集。
• n ≤ 300000。
• 0 ≤ a[i] < 2^18。

eg: A=1110111000 B=1000011000 B是A的子集

暴力解法

• 动态规划，设f[i]表示有多少满足条件的序列以a[i]为结尾。
• f[i] = 1 + sum(f[j])，其中j<i且a[j]包含a[i]。
• ans = sum(f[i]) - n。
• 时间复杂度O(n²)，不能接受。

分块解法

• 将序列分块，每块size个数。
• 对于f[i]的计算，暴力枚举块内所有j，更新f[i]。
• 每算完一块的所有f的值时，设g[x]表示前面所有数中，包含x的数的f的和。
• 则g可以由高维前缀和在O(a log a)的时间内算出。

18维度前缀和

• 一共要重新计算n/size次g。
• 时间复杂度O(n/size*a*log(a)+n*size)。
• 当size=sqrt(a log a)时取得最小值O(n*sqrt(a log a))。

正解

• \(0 \leq a[i] < 2^{18}\)，故二进制下一共18位。
• 设g[x][y]表示前9位为x的数对后9位为y的DP值的贡献。
• 要计算f[i]时，令A为a[i]的前9位，B为a[i]的后9位，则f[i]=1+sum(g[x][B])，其中x包含A。
• 计算完毕f[i]后，将所有的g[A][y]都加上f[i]，其中B包含y。
• 时间复杂度O(n*sqrt(a))。