题解：P13976 数列分块入门 1

· · 题解

:::epigraph[Shellchen] 大家好呀，今天我来给大家讲分块！ :::

分块是一种数据结构，通过把数列分成若干块来处理问题。区间加法，单点查询是分块最基本的一种问题。

分块的过程如下：

首先我们需要有一个数列，把它分成若干个等长的块。最后一块可以稍短。就像这样：

1 4 7/2 5 8/3 6 9/10 12

接下来，我们可以这么处理区间加法：先给范围内所有完整的块加上 c，在将剩余部分加上 c 即可。

这里需要用到一个 trick：懒标记思想。我们只需要对于中间所有完整块打上一个标记，就代表整个块加上了这个数，之后单点查值的时候就可以用单点的值加上这个 tag 了。不是完整块的部分暴力加即可。

那么，如何找完整块呢？设块长为 k，那么块头的下标 \mod k 一定等于 1。于是可以直接暴力查找第一个，之后每次加 k，直到加了 k 之后下标会超过 r 为止。我们只要把整块的 tag 打在块头就行。这样就处理好了打 tag 方法的问题。单点查询的时候暴力找块头就行。

这样下来，修改复杂度是 O(k+n/k)，查询复杂度是 O(k)。实际使用时 k 一般取 \sqrt n，总复杂度 O(n \sqrt n)。

最后，要是还没有看懂，那就只能上绝招了，上代码！

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+10,mod=1e9+7;
int a[N],tag[N]; 
signed main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int k=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        int op,l,r,c;
        cin>>op>>l>>r>>c;
        if(op==0)
        {
            int i=l;
            for(;i%k!=1&&i<=r;i++) a[i]+=c;
            for(;i<=r-k;i+=k) tag[i]+=c;
            for(;i<=r;i++) a[i]+=c;
        }
        else
        {
            int i=r;
            for(;i%k!=1;i--);
            cout<<a[r]+tag[i]<<'\n';
        }
    }
    return 0;
}

完结撒花。

:::epigraph[Shellchen] 讲完了，下课！ :::