数列分块

lfxxx_ · 2024-04-10 17:32:06 · 算法·理论

数列分块

定义

数列分块，本质上是一个思想，指把一个长度 n 的数列分成 t 块再处理，能处理比线段树一类的数据结构多的问题，不过平均复杂度比线段树差一点。我们通常会把 t 赋值为 \sqrt{n}，这样子就是 O(n \sqrt{n}) 的

基本操作

查询

• 情况1：如果查询区间比 \frac{t}{n} 小，则直接暴力去查询。

• 情况2：如果查询区间比 \frac{t}{n} 大，则先处理两边比 \frac{t}{n} 小的部分，再处理中间的整块

修改

• 情况1：如果修改区间比 \frac{t}{n} 小，则直接暴力去修改。
• 情况2：如果修改区间比 \frac{t}{n} 大，则先处理两边比 \frac{t}{n} 小的部分，再给中间的整块打上懒标记。

实现

例题1：P3372 线段树1

思路

分块模板题。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int L[N],R[N],pos[N];
int a[N],sum[N],tag[N];//基本的分块数组
void add(int l,int r,int d)
{
    int x=pos[l],y=pos[r];
    if(x==y)
    {
        for(int i=l;i<=r;++i)
            a[i]+=d,sum[x]+=d;//暴力修改
        return ;
    }
    for(int i=x+1;i<=y-1;++i)
        tag[i]+=d,sum[i]+=(R[i]-L[i]+1)*d;//打上懒标记
    add(l,R[x],d);//修改零散块
    add(L[y],r,d);
}
int query(int l,int r)
{
    int x=pos[l],y=pos[r],ans=0;
    if(x==y)
    {
        for(int i=L[x];i<=R[x];++i)//懒标记下传
            a[i]+=tag[x];
        for(int i=l;i<=r;++i)//暴力处理
            ans+=a[i];
        tag[x]=0;
        return ans;
    }
    for(int i=L[x];i<=R[x];++i)
        a[i]+=tag[x];//懒标记下传
    for(int i=L[y];i<=R[y];++i)
        a[i]+=tag[y];
    for(int i=l;i<=R[x];++i)//零散块查询
        ans+=a[i];
    for(int i=L[y];i<=r;++i)
        ans+=a[i];
    for(int i=x+1;i<y;++i)//整块查询
        ans+=sum[i];
    tag[x]=tag[y]=0;//清空懒标记
    return ans;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    int t=sqrt(n);//初始化块
    for(int i=1;i<=t;++i)
    {
        L[i]=R[i-1]+1;
        R[i]=i*t;
    }
    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)
        {
            sum[i]+=a[j];
            pos[j]=i;
        }//累加并记录每个点所在块
    while(m--)
    {
        int op,l,r;
        cin>>op>>l>>r;
        if(op==1)
        {
            int d;
            cin>>d;
            add(l,r,d);
        }
        else
        {
            cout<<query(l,r)<<'\n';
        }
    }
}