『分块算法初步』

墨蓝 2021-12-21 20:59 230阅读 0赞

--------------------

## 分块 ##

> 分块查找是折半查找和顺序查找的一种改进方法，分块查找由于只要求索引表是有序的，对块内节点没有排序要求，因此特别适合于节点动态变化的情况。

分块其实可以说是一种偏数据结构类的通用型算法吧，没有很艰深的内容，与暴力最为相似，但是在很多题目中都能派上很好的用场。

我们可以先通过一道模板例题来了解分块。

### Description ###

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

### Solution ###

这道题当然可以用树状数组，线段树等经典的数据结构来解决，我们现在来谈一谈分块的做法。

分块就是讲原本序列中的n个数"打包"分为\\(sqrt(n)\\)个块，对于区间的操作，我们可以对每一个块进行标记处理，等到查询时再检查是否有更新记录，利用类似于这样的思想来优化时间复杂度。

具体的，我们可以这样做。

> 1.使\\(t=sqrt(n)\\)，将原序列分为\\(t\\)个块，其中，第\\(i\\)个块的覆盖范围为\\(\[(i-1)\*t+1,i\*t\]\\)  
> 2.对于最后剩下不完全的部分，额外的分一个块，其范围为\\(\[n-\\lfloor\{\\frac\{n\}\{t\}\}\\rfloor\*t+1,n\]\\)  
> 3.预处理一个数组\\(pos\[i\]\\)，代表第\\(i\\)个元素所在块的下标  
> 4.对于区间加法操作，区间包含的部分一定为若干个完整的块(可能\\(0\\)个)和至多两个不完整的块，对于不完整的块，我们可以暴力扫描进行加法更新，对于完整的块\\(i\\)，我们可以令\\(changed\[i\]+=delta\\)，表示第i个块有一个整体的\\(+delta\\)更新操作，先记录下来。  
> 5.对于查询操作，我们可以直接返回\\(a\[x\]+change\[pos\[x\]\]\\)。

这就是分块算法的基本流程，引用\\(lyd\\)大佬一句话来形容，就是**大段维护，局部朴素**，可以认为是暴力的优化，具有较好的直观性，代码量不长，容易拓展。

\\(Code:\\)

#include<bits/stdc++.h>
    using namespace std;
    const int N=100000+200,M=100000+200,sqrtN=400;
    int n,t,L[sqrtN],R[sqrtN],pos[N];
    long long changed[sqrtN],a[N];
    inline void input(void)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%lld",&a[i]);
    }
    inline void init(void)
    {
        t=sqrt(n);
        for(int i=1;i<=t;i++)
        {
            L[i]=(i-1)*sqrt(n)+1;
            R[i]=i*sqrt(n);
        }
        if(R[t]<n)t++,L[t]=R[t-1]+1,R[t]=n;
        for(int i=1;i<=t;i++)
            for(int j=L[i];j<=R[i];j++)
                pos[j]=i;
    } 
    inline void change(int l,int r,long long delta)
    {
        int p=pos[l],q=pos[r];
        if(p==q)
            for(int i=l;i<=r;i++)a[i]+=delta;
        else
        {
            for(int i=p+1;i<=q-1;i++)
                changed[i]+=delta;
            for(int i=l;i<=R[p];i++)
                a[i]+=delta;
            for(int i=L[q];i<=r;i++)
                a[i]+=delta;
        }
    }
    inline long long ask(int x)
    {
        return a[x]+changed[pos[x]];
    }
    inline void solve(void)
    {
        int index,l,r;long long delta;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d%lld",&index,&l,&r,&delta);
            if(!index)
                change(l,r,delta);
            else printf("%lld\n",ask(r));
        }
    } 
    int main(void)
    { 
        input();
        init();
        solve();
        return 0;
    }

### Description ###

给出一个长为\\(n\\)的数列，以及\\(n\\)个操作，操作涉及区间加法，询问区间内小于某个值\\(x\\)的元素个数。

### Solution ###

这道题就是分块算法的简单拓展，对原来算法进行简单的改进就可以解决该问题。

除了增量标记外，每一个块我们额外维护一个有序序列。用\\(vector\\)储存每一个块的有序序列并直接利用\\(sort\\)排序即可。

对于区间加法，整块的部分直接累加增量标记，非整块的部分暴力修改单点权值，并对部分修改的块重置有序序列即可。  
对于查询，整块的部分直接二分查找有序序列中大小第一个大于等于\\(c\*c-change\[i\]\\)的部分，数量即为该位置减掉数组首地址，累加每一个整块的数量即可，非整块的部分暴力统计即可累加答案。

\\(Code:\\)

#include<bits/stdc++.h>
    using namespace std;
    const int N=50000+200,M=50000+200,sqrtN=300;
    int n,t,L[sqrtN],R[sqrtN],pos[N];
    int changed[sqrtN],a[N];
    vector < int > section[sqrtN];
    inline void input(void)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
    }
    inline void reset(int x)
    {
        section[x].clear();
        for(int i=L[x];i<=R[x];i++)
            section[x].push_back(a[i]);
        sort(section[x].begin(),section[x].end()); 
    }
    inline void init(void)
    {
        t=sqrt(n);
        for(int i=1;i<=t;i++)
        {
            L[i]=(i-1)*sqrt(n)+1;
            R[i]=i*sqrt(n);
        }
        if(R[t]<n)t++,L[t]=R[t-1]+1,R[t]=n;
        for(int i=1;i<=t;i++)
            for(int j=L[i];j<=R[i];j++)
                pos[j]=i;
        for(int i=1;i<=t;i++)
            reset(i);
    }
    inline void change(int l,int r,int delta)
    {
        int p=pos[l],q=pos[r];
        if(p==q)
        {
            for(int i=l;i<=r;i++)
                a[i]+=delta;
            reset(p);
        }
        else
        {
            for(int i=l;i<=R[p];i++)
                a[i]+=delta;
            reset(p);
            for(int i=L[q];i<=r;i++)
                a[i]+=delta;
            reset(q);
            for(int i=p+1;i<=q-1;i++)
                changed[i]+=delta; 
        }
    } 
    inline int ask(int l,int r,int limit)
    {
        int p=pos[l],q=pos[r];
        int ans=0;
        if(p==q)
        {
            for(int i=l;i<=r;i++)
                if(a[i]+changed[p]<limit)ans++;
        }
        else
        {
            for(int i=l;i<=R[p];i++)
                if(a[i]+changed[p]<limit)ans++;
            for(int i=L[q];i<=r;i++)
                if(a[i]+changed[q]<limit)ans++;
            for(int i=p+1;i<=q-1;i++)
                ans+=lower_bound(section[i].begin(),section[i].end(),limit-changed[i])-section[i].begin();
        }
        return ans;
    }
    inline void solve(void)
    {
        int l,r,index;int delta;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d%d",&index,&l,&r,&delta);
            if(!index)
                change(l,r,delta);
            else printf("%d\n",ask(l,r,delta*delta)); 
        }
    }
    int main(void)
    {
        input();
        init();
        solve();
        return 0;
    }

### Description ###

给出一个长为\\(n\\)的数列，以及\\(n\\)个操作，操作涉及区间加法，询问区间内小于某个值\\(x\\)的前驱（比其小的最大元素）。

### Solution ###

这道题其实和第二题类似，也是维护每一个块的区间有序性，前驱直接二分查找即可。

\\(Code:\\)

#include<bits/stdc++.h>
    using namespace std;
    const int N=100000+200,sqrtN=400;
    const long long INF=LONG_LONG_MAX;
    int n,t,L[sqrtN],R[sqrtN],pos[N];
    long long changed[sqrtN],a[N];
    vector < long long > section[sqrtN];
    inline void input(void)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%lld",&a[i]);
    }
    inline void reset(int x)
    {
        section[x].clear();
        for(int i=L[x];i<=R[x];i++)
            section[pos[i]].push_back(a[i]);
        sort(section[x].begin(),section[x].end());
    }
    inline void init(void)
    {
        t=sqrt(n);
        for(int i=1;i<=t;i++)
        {
            L[i]=(i-1)*sqrt(n)+1;
            R[i]=i*sqrt(n);
        }
        if(R[t]<n)t++,L[t]=R[t-1]+1,R[t]=n;
        for(int i=1;i<=t;i++)
            for(int j=L[i];j<=R[i];j++)
                pos[j]=i;
        for(int i=1;i<=t;i++)
            reset(i);
    }
    inline void change(int l,int r,long long delta)
    {
        int p=pos[l],q=pos[r];
        if(p==q)
        {
            for(int i=l;i<=r;i++)
                a[i]+=delta;
            reset(p);
        }
        else
        {
            for(int i=l;i<=R[p];i++)
                a[i]+=delta;
            reset(p);
            for(int i=L[q];i<=r;i++)
                a[i]+=delta;
            reset(q);
            for(int i=p+1;i<=q-1;i++)
                changed[i]+=delta;
        }
    }
    inline void updata(long long &ans,long long val,long long limit)
    {
        if(val<limit&&val>ans)ans=val;
    }
    inline long long ask(int l,int r,long long limit)
    {
        int p=pos[l],q=pos[r];
        long long ans=-1;
        if(p==q)
        {
            for(int i=l;i<=r;i++)
                updata(ans,a[i]+changed[pos[i]],limit);
        }
        else
        {
            for(int i=l;i<=R[p];i++)
                updata(ans,a[i]+changed[pos[i]],limit);
            for(int i=L[q];i<=r;i++)
                updata(ans,a[i]+changed[pos[i]],limit);
            for(int i=p+1;i<=q-1;i++)
                updata(ans,section[i][lower_bound(section[i].begin(),section[i].end(),limit-changed[i])-section[i].begin()-1]+changed[i],limit);
        }
        return ans;
    }
    inline void solve(void)
    {
        int l,r,index;long long delta;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d%lld",&index,&l,&r,&delta);
            if(!index)
                change(l,r,delta);
            else printf("%lld\n",ask(l,r,delta)); 
        }
    }
    int main(void)
    {
        input();
        init();
        solve();
        return 0;
    }

### Description ###

给出一个长为\\(n\\)的数列，以及\\(n\\)个操作，操作涉及区间加法，区间求和。

### Solution ###

这道题的拓展也是比较典型的。我们只需要再维护每一块的权值和就可以快速的解决查询问题，对于权值和的更新，只需要对每一次加法操作是进行顺带更新即可。

\\(Code:\\)

#include<bits/stdc++.h>
    using namespace std;
    const int N=100000+200,M=100000+200,sqrtN=400;
    int n,t,L[sqrtN],R[sqrtN],pos[N];
    long long changed[sqrtN],sum[sqrtN],a[N];
    inline void input(void)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%lld",&a[i]);
    }
    inline void init(void)
    {
        t=sqrt(n);
        for(int i=1;i<=t;i++)
        {
            L[i]=(i-1)*sqrt(n)+1;
            R[i]=i*sqrt(n);
        }
        if(R[t]<n)t++,L[t]=R[t-1]+1,R[t]=n;
        for(int i=1;i<=t;i++)
            for(int j=L[i];j<=R[i];j++)
                pos[j]=i,sum[i]+=a[j];
    } 
    inline void change(int l,int r,long long delta)
    {
        int p=pos[l],q=pos[r];
        if(p==q)
        {
            for(int i=l;i<=r;i++)a[i]+=delta;
            sum[p]+=delta*(r-l+1);
        }
        else
        {
            for(int i=p+1;i<=q-1;i++)
                changed[i]+=delta;
            for(int i=l;i<=R[p];i++)
                a[i]+=delta;
            sum[p]+=delta*(R[p]-l+1);
            for(int i=L[q];i<=r;i++)
                a[i]+=delta;
            sum[q]+=delta*(r-L[q]+1); 
        }
    }
    inline long long ask(int l,int r,long long mod)
    {
        int p=pos[l],q=pos[r];
        long long ans=0;
        if(p==q)
        {
            for(int i=l;i<=r;i++)ans+=a[i];
            ans+=changed[p]*(r-l+1);
            ans%=mod;
        }
        else
        {
            for(int i=p+1;i<=q-1;i++)
                ans+=sum[i]+changed[i]*(R[i]-L[i]+1),ans%=mod;
            for(int i=l;i<=R[p];i++)
                ans+=a[i],ans%=mod;
            ans+=changed[p]*(R[p]-l+1),ans%=mod;
            for(int i=L[q];i<=r;i++)
                ans+=a[i],ans%=mod;
            ans+=changed[q]*(r-L[q]+1),ans%=mod;
        }
        return ans;
    }
    inline void solve(void)
    {
        int l,r,index;long long delta;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d%lld",&index,&l,&r,&delta);
            if(!index)
                change(l,r,delta);
            else printf("%lld\n",ask(l,r,delta+1)%(delta+1));
        }
    } 
    int main(void)
    {
        input();
        init();
        solve();
        return 0;
    }

## 总结 ##

分块算法可以说是一种优雅的暴力优化，在处理区间问题上有很大的帮助，通过对几道例题的认识，我们可以归纳得到如下要点：

*  是否可以用分块算法？区间问题，具有整体维护的可行性
 *  使用分块算法需要考虑的问题？1.如何预处理 2.如何处理不完整的块 3.如何维护完整的块

--------------------

转载于:https://www.cnblogs.com/Parsnip/p/10458689.html