题解：P13976 数列分块入门 1

· · 题解

分块思想

如题，本题可以用分块解决。

当然也可以用线段树、树状数组等数据结构，这里不作介绍。

数列分块，就是把序列分成一个一个块去处理区间问题。对于一段区间 [l,r]，我们可以拆成许多整块和头尾两部分散块去处理问题。

如上图，区间 [l,r] 可以拆成三个黄色的整块和两端蓝色的散块进行处理。

对于本题而言，考虑如下做法：

令每一块的块长为 B（最后一块可能取不到，因为右端点是 n）。

对于区间修改操作，我们将修改区间分为两部分：

对于单点查询，拿该元素的值加上整块加时维护的懒标记，就是查询的答案。

综上，该算法的总时间复杂度为 O(n(B+\dfrac nB))。根据二元均值不等式，当 B=\sqrt n 时 B+\dfrac nB 的值最小，为 2\sqrt n，因此取 B=\sqrt n，该算法的时间复杂度为 O(n\sqrt n)。

为什么要有分块

本题可以用线段树等数据结构做到 O(n\log n) 的时间复杂度，那么为什么我们需要复杂度更劣的分块呢？原因在于线段树可以维护的结构必须满足可以合并的性质。而分块并不需要执行信息的合并，所以分块的泛用性更广。

代码实现

对于每个元素，我们需要知道它所在的块。对于每个块，我们需要知道它管辖的区间 [\text{minn},\text{maxn}]。我们先实现预处理。

通过简单的推式子可以得到：

for(int i=1;i<=n;i++){
    cin>>a[i];
    id[i]=(i-1)/B+1;//所在块编号（每B个元素在一个块）
    minn[i]=(id[i]-1)*B+1;//所在块左端点
    maxn[i]=min(n,id[i]*B);//所在块右端点
}

接下来实现区间修改。记录 tag[i] 表示编号为 i 的块的懒标记。

if(opt==0){
    for(int i=id[l]+1;i<=id[r]-1;i++)tag[i]+=c;//整块打标记
    for(int i=l;i<=min(r,maxn[l]);i++)a[i]+=c;//散块暴力加
    if(id[l]!=id[r]){//特别注意要保证没有多加
        for(int i=max(l,minn[r]);i<=r;i++)a[i]+=c; 
    }
}

查询就非常简单了。

cout<<a[r]+tag[id[r]]<<endl;

完整代码如下：

#include<iostream>
#include<cmath>
#define int long long
using namespace std;
int n,B;
int a[300005];
int minn[300005],maxn[300005],id[300005];
int tag[300005];
signed main(){
    cin>>n;
    B=sqrt(n);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        id[i]=(i-1)/B+1;
        minn[i]=(id[i]-1)*B+1;
        maxn[i]=min(n,id[i]*B);
    }
    for(int j=1;j<=n;j++){
        int opt,l,r,c;
        cin>>opt>>l>>r>>c;
        if(opt==0){
            for(int i=id[l]+1;i<=id[r]-1;i++)tag[i]+=c;
            for(int i=l;i<=min(r,maxn[l]);i++)a[i]+=c;
            if(id[l]!=id[r]){
                for(int i=max(l,minn[r]);i<=r;i++)a[i]+=c; 
            }
        }
        if(opt==1){
            cout<<a[r]+tag[id[r]]<<endl;
        }
    }
    return 0;
}