分块思想

· · 算法·理论

分块思想

简介

将一个序列进行适当划分，将每一个小块依照题意进行预处理，将暴力算法进行优化。

所以，分块思想可以说是比较高级的暴力。

分块思想很灵活，相比较于树状数组或者是线段树，它的代码量较短，而且很通用。缺点是，在遇到大量的数据维护的时候，分块的时间复杂度可能无法智齿我们去 AC 这道题。

例题

题目描述

给出一个长为n 的数列，以及 n 个操作，操作涉及区间加法，单点查值。

输入格式

第一行输入一个数字 n。

第二行输入 n 个数字，第 i 个数字为 a_i，以空格隔开。

接下来输入 n 行询问，每行输入四个数字 opt, l,r,c，以空格隔开。

若 opt=0，表示将位于 [l,r] 之间的数字都加上 c。

若 opt=1，表示询问 a_r 的值（l 和 c 忽略）。

数据范围

对于 100% 的数据，1 \le n \le 50000,-2^{31} \le others,ans \le 2^{31}-1。

输出格式

对于每次询问，输出一行一个数字表示答案。

分析

这题如果用暴力做的话，区间加法的复杂度为 O(n^2)，很显然会炸，所以我们考虑用分块思想优化。

如图所示，数轴上每一个小格子代表一个块，假设我们要对序列中的红色部分进行修改，此时，选中部分可以被分为蓝色（左边一小块）、绿色（中间的整块）、橙色（右边一小块）三个区域。

蓝色和橙色部分数量很小，所以可以将两个区域直接暴力解决。

绿色部分都是完整的块，我们不需要再用循环一个一个加，这样就和暴力没有区别了。我们可以建立一个 add[] 数组，记录每个整块在修改时加的数量，这个思想叫做延迟标签（LazyTag）。

每次修改的时候，我们可以将绿色部分的块所对应的 add[] 标签加上 c，在查询的时候，只需要再把这个数所属的区块的 add[] 标签加上去就可以了。

（其实这题也可以用树状数组做）

参考代码

#include<bits/stdc++.h>
using namespace std;
const int N=50005,M=250;
int n,s,a[N],add[M];
void addition(int l,int r,int c){ // 区间加法
    if(r-l<s){
        for(int i=l;i<=r;i++)
            a[i]+=c;
        return; // 如果区间在同一个区块里就直接暴力
    }
    for(int i=l;i<=((l-1)/s+1)*s;i++) // 蓝色区域处理
            a[i]+=c;
    for(int i=(l-1)/s+2;i<=r/s;i++) // 绿色区域处理
            add[i]+=c;
    for(int i=(r/s)*s+1;i<=r;i++) // 橙色区域处理
            a[i]+=c;
}
int main(){
    scanf("%d",&n);
    s=sqrt(n); // 一般区块长度取 sqrt(n) 是效率最高的
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int q=1;q<=n;q++){
        int op,l,r,c;
        scanf("%d%d%d%d",&op,&l,&r,&c);
        if(!op)
            addition(l,r,c);
        else
            printf("%d\n",a[r]+add[(r-1)/s+1]); // 把原来的数和延迟标签记录的和输出
    }
    return 0;
}