分块学习笔记

shiroi · 2019-10-28 21:44:50 · 个人记录

分块是将整个区间分成若干块，维护整块的信息，以加速查询。平时能遇到的分块题基本上都是不满足结合律的操作，因此不能用线段树维护。

基本概念

区间：数列中连续一段的元素

区间操作：将某个区间[a,b]的所有元素进行某种改动的操作

块：我们将数列划分成若干个不相交的区间，每个区间称为一个块

整块：在一个区间操作时，完整包含于区间的块

不完整的块：在一个区间操作时，只有部分包含于区间的块，即区间左右端点所在的两个块

分块基础

我们把每次操作完整覆盖的块定义为“整块”

把每次操作没有完整覆盖的块定义为“零散块”

每次操作最多经过O(\sqrt n)个整块以及O(1)个零散块。
所以我们可以O(1)维护整块信息，O(\sqrt n)地维护零散块信息。这样总的时间复杂度就达到了O(n\sqrt n)。
如果在分治结构上很难快速合并某些信息，我们就可以利用分块来做。
比如区间数颜色、区间众数等等不满足区间可加性的操作。

具体实现

分块实现的基本框架：
划分块、预处理、操作/查询。

操作或查询通常为4步：

单独暴力处理最左端的边角块
判断要操作或是查询的区间是否在一个块内
若在一个块内，暴力处理最右边的边角块
若不在一个块内，将除了最左边和最右边这两个块外其余的块进行整体操作，即直接对块打上修改标记等

同时分块的块内还可以使用别的数据结构或是操作以实现题目要求或进一步优化复杂度

代码实现

例题：【模板】线段树1

这题的询问是区间上的询问。对于不完整的块还是暴力处理；而要快速统计完整块的答案，需要维护每个块的元素和，先要预处理一下。

考虑区间修改操作，不完整的块直接修改，同时更新块的元素和；完整的块类似打标记的做法，直接根据块的元素和所加的值计算元素和的增量。

#include <bits/stdc++.h>
using namespace std;

inline long long read()
{
    long long x=0;long long f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

const int MAXN = 100005;
long long bl[MAXN],dat[MAXN],tag[MAXN],sum[MAXN];
int n,m,block;

void add(long long a,long long b,long long c)
{
    for(int i=a;i<=min(bl[a]*block,b);i++)
        dat[i]+=c,sum[bl[a]]+=c;;
    if(bl[a]!=bl[b])
        for(int i=(bl[b]-1)*block+1;i<=b;i++)
            dat[i]+=c,sum[bl[b]]+=c;
    for(int i=bl[a]+1;i<=bl[b]-1;i++)
        tag[i]+=c;
}

long long query(long long a,long long b)
{
    long long ans=0;
    for(int i=a;i<=min(bl[a]*block,b);i++)
        ans+=dat[i]+tag[bl[a]];
    if(bl[a]!=bl[b])
        for(int i=(bl[b]-1)*block+1;i<=b;i++)
            ans+=dat[i]+tag[bl[b]];
    for(int i=bl[a]+1;i<=bl[b]-1;i++)
        ans+=sum[i]+block*tag[i];
    return ans;
}

int main(int argc, char const *argdat[])
{
    n=read(); m=read(); block=sqrt(n);
    for(int i = 1; i <= n; ++i) dat[i]=read();
    for(int i = 1; i <= n; ++i)
    {
        bl[i]=(i-1)/block+1;
        sum[bl[i]]+=dat[i];
    }
    int opt,x,y;
    for(int i = 1; i <= m; ++i)
    {
        opt=read(),x=read(),y=read();
        if(opt==1) add(x,y,read());
        if(opt==2) printf("%lld\n",query(x,y));
    }
    return 0;
}

分块学习笔记

基本概念

分类

分块基础

具体实现

代码实现